# Sorting – Set 1

9, 10, 26, 27

1. Given an array of n distinct elements. Check whether the given array is a k sorted array or not. A k sorted array is an array where each element is at most k distance away from its target position in the sorted array. GFG.
Algo:
Copy the array into another array and sort it. Then for every element in the unsorted array do a binary search in sorted array. We have the index where it’s found in sorted array and the index in which it is present in unsorted array. Compare these.
Time Complexity: O(nlogn)
Auxiliary space: O(n)

2. Given two arrays of equal size N, form maximum number of pairs by using their elements, one from the first array and second from the second array, such that an element from each array is used at-most once and the absolute difference between the selected elements used for forming a pair is less than or equal to a given element K. GFG.
Algo: Sort both the arrays and then compare each element from the starting using two pointers(one for each array). Move the pointers accordingly.

3. ** Find shortest unique prefix for every word in a given list. GFG
Algo: Use trie.
1) Construct a Trie of all words. Also maintain frequency of every node (Here frequency is number of times node is visited during insertion). Time complexity of this step is O(N) where N is total number of characters in all words.
2) Now, for every word, we find the character nearest to the root with frequency as 1. The prefix of the word is path from root to this character. To do this, we can traverse Trie starting from root. For every node being traversed, we check its frequency. If frequency is one, we print all characters from root to this node and don’t traverse down this node.
Time complexity if this step also is O(N) where N is total number of characters in all words.

4. ***** Longest Common Prefix using Sorting.  GFG
Algo: The longest common prefix for an array of strings is the common prefix between 2 most dissimilar strings. For example, in the given array {“apple”, “ape”, “zebra”}, there is no common prefix because the 2 most dissimilar strings of the array “ape” and “zebra” do not share any starting characters.
The most dissimilar words will be first and the last word a sorted array. So we can focus on those words. So we can keep checking for the common char in the first and last word until the string is over or there’s something dis-similar.
We have discussed five different approaches in below posts.

1. Word by Word Matching
```LCP(string1, string2, string3)
= LCP (LCP (string1, string2), string3)
LCP (“geeksforgeeks”, “geeks”, “geek”)
=  LCP (LCP (“geeksforgeeks”, “geeks”), “geek”)
=  LCP (“geeks”, “geek”) = “geek”```
2. Character by Character Matching
In this algorithm, instead of going through the strings one by one, we will go through the characters one by one.
3. Divide and Conquer
4. Binary Search.
5. Using Trie

5. Given an array of n distinct integers. The problem is to find the sum of minimum absolute difference of each array element. For an element x present at index i in the array its minimum absolute difference is calculated as:
Min absolute difference (x) = min(abs(x – arr[j])), where 1 <= j <= n and j != i and abs is the absolute value. GFG
read the question properly and take a proper example.
Algo: In a sorted array the minimum absolute difference of each array element at index i, will be with either element at i-1 or i+1 (except for first and last element).
So sort the array and apply the logic.

6. ** Given a sequence of n strings, the task is to check if any two similar words come together then they destroy each other then print the number of words left in the sequence after this pairwise destruction. GFG
Algo:
1. Sort the array. All similar words will be grouped together. Then traverse the array and remove the duplicate one( they will be next to each other). The best way to remove the string will be to use remove method of the Java collection. Check this SO postDelete
2. Use Stack. Start traversing the strings and push into stack.  Check if the current string is same as the string at the top of the stack. If yes, pop the string from top. Else push the current string. Return the original stack size.

7. Sort elements on the basis of number of factors – Given an array of positive integers. Sort the given array in decreasing order of number of factors of each element, i.e., element having the highest number of factors should be the first to be displayed and the number having least number of factors should be the last one. Two elements with equal number of factors should be in the same order as in the original array. GFG
Dependent: Find the number of factors of each number(this can be done in sqrt(n) time for each number, GFG).
Algo: Then we store the number and number_of_factor together and then sort on basis of factors count.
Check the code. The comparator part of the code is worth noticing.
O(n.sqrt(m) + n.lg(n)) such that n is the size of the array and m is the largest element.

8. Given an array of n strings. The task is to print the strings in sorted order. The approach should be such that no string should be copied to another string during sorting process. GFG
Algo: Here we need to implement any selection sorting technique to work with String. We can’t copy string so how do we sort ?  We maintain an array where we maintain the index of the sorting array in order. So if [1, 4, 0, 3, 2 ], then string at 1 in given array should be first element in the sorted array and so on.
*SO – comapreTo details. Worth a read.
We will use compateTo() in java.  The return of this method is an `int` which can be interpreted as follows:

• “aaa”.compareTo(“abc”) – returns < 0 then the String calling the method is lexicographically first (comes first in a dictionary)
• “aaa”.compareTo(“aaa”), returns == 0 then the two strings are lexicographically equivalent
• “abc”.compareTo(“aaa”), returns > 0 then the parameter passed to the `compareTo` method is lexicographically first.

9. *** We have an integer array that is sorted in ascending order. We also have 3 integers A, B and C. We need to apply A*x*x + B*x + C for each element x in the array and sort the modified array. GFG . Adobe
Algo:
Algo 1. Apply the given equation to every array element and then sort.Time complexity of O(n log n)
Algo 2.  The equation given is parabolic.The concept is important here – we can merge two sorted array in O(n).
The result of the above equation will be a parabola, which will have a peak about a point. All the numbers on the either side will be sorted. So the idea is to merge these two already sorted array using merge sort logic.

In the above example, maximum is 0 and the sub array to its left {-4, -1} is sorted in ascending order and the sub-array to its right {-1, -4, -9} is sorted in descending order.  All we need to do is merge these sorted arrays which is linear in time.
So the algorithm is:
Apply equation on each element.
Find maximum/minimum.
Merge sub-arraysTime Complexity : O(n) Auxiliary Space : O(n)

10. *** We are given an unsorted array of integers in the range from 0 to n-1. We are allowed to swap adjacent elements in array many number of times but only if the the absolute difference between these element is 1. Check if it is possible to sort the array.If yes then print “yes” else “no”. GFG
Algo: Okay, let’s look at it in a different way.
1. We can swap only if the a[i] > a[i+1], else no need to swap.
2. If rule 1 is true, we can swap only if the diff of (a[i] – a[i+1]) == 1
3. If the diff is anything other than 1, then the array can’t be sorted. We end the program.
So we start traversing the array. We verify the rule 1.  If it’s true we check rule 2, if that’s true and rule 3 is false then the array can’t be sorted. End.
If rule 1 is never satisfied it means the array was already sorted.

11. We are given an array of strings, we need to sort the array in increasing order of string lengths.  GFG Code
Algo: We can override the default java sort method to work with length(write a comparator).
When writing a comparator, note that if the compare method returns negative, that result will come first (same as string compareTo).

12. Given two arrays of integers, compute the pair of values (one value in each array) with the smallest (non-negative) difference. Return the difference. GFG.
Algo: Sort both array and then set a pointer at the beginning of both arrays and keep finding the minimum difference and moving the pointer accordingly.

13. Program to print an array in Pendulum Arrangement – Read full details on the page  GFG
Algo: Sort the array. Then create a new auxiliary array and start placing these element from sorted array in correct position.

14. * Given an array of size n, write a program to check if it is sorted in ascending order or not. Equal values are allowed in array and two consecutive equal values are considered sorted. GFG. Handle the duplicate
Algo:
1. Iterative is pretty simple.
2. ** The recursive method will take a and length of the array as input. In each recursive call the length of array starts decreasing (the index which needs to be checked ). For recursive our base will be that the size of the array is 0 or 1.

15. Given an array arr[], find a Noble integer in it. An integer x is said to be Noble in arr[] if the number of integers greater than x are equal to x. If there are many Noble integers, return any of them. If there is no, then return -1. GFG
Algo: Just sort the array and count. O(nlog(n))

16. **** Find the largest multiple of 3 from array of digits in n O(n) time and O(1) space. GFG
Algo:  We can sort a array for which the range of value is known using count sort in O(n). We know that a number is divisible by 3 if the sum of digit is divisible by 3. If it’s not then we will have to remove the digit(s) equal to the remainder.
The digit that we remove will be the smallest one, if we want the largest number. There are two cases on how to remove the remainder –
–  If remainder is ‘1’ : We have to remove single digit that have remainder ‘1’ or we have to remove two digit that have remainder ‘2’ ( 2 + 2 => 4 % 3 => ‘1’
–  If remainder is ‘2’ : .We have to remove single digit that have remainder ‘2’ or we have to remove two digit that have remainder ‘1’ ( 1 + 1 => 2 % 3 => 2 ).

17. Given an integer array with repeated elements, the task is to find sum of all distinct elements in array. GFG
Algo:
1. Sorting.   Time Complexity : O(n log n) Space Complexity : O(1)
2. Hashing. Time Complexity : O(n) Auxiliary Space : O(n)

18. Given an array with n distinct elements, convert the given array to a form where all elements are in range from 0 to n-1. The order of elements is same, i.e., 0 is placed in place of smallest element, 1 is placed for second smallest element, … n-1 is placed for largest element. GFG
Algo: The order is same, ie. 0 is placed in place of smallest element and 1 is placed in place of second smallest and so on..
Create a copy of given array and Sort it. Create a map and store the element as key and index as value. Then traverse the main array and get the index of the element in the sorted array form hashmap and update the main array.

19. [Pending] Minimum swaps to reach permuted array with at most 2 positions left swaps allowed

20. Given an array of integer values, we need to find the minimum difference between maximum and minimum of all possible K-length subsets. GFG
Algo: Sorting followed by sliding window concept.

21. * Given three inte­gers, print them in sorted order with­out using if condition. GFG
Algo: We can’t use if condition but we can use in-built max function. Simple –
get_max = Math.max(a, max(b, c));
get_min = -Math.max(-a, max(-b, -c));

22. Given an array of numbers where every number is represented as string. The numbers may be very large (may not fit in long long int), the task is to sort these numbers. GFG Code
Algo: Comparator function. It will work on the basis of length. If length is same then simple comparison.

23. *** Sorting Big Integers – Given a array of n positive integers where each integer can have digits upto 10^6, print the array elements in ascending order. GFG
Algo:  Same as above(see the code). A naive approach is to use arbitrary precision data type such as Biginteger class in Java. But that approach will not be fruitful because internal conversion of string to int and then perform sorting will leads to slow down the calculations of addition and multiplications in binary number system.  We need to define our own comparator function to apply the logic. Following are the key points compare function:-

1. If lengths of two strings are different, then we need to compare lengths to decide sorting order.
2. If Lengths are same then we just need to compare both the strings in lexicographically order.

24. Given an array of integers (both odd and even), sort them in such a way that the first part of the array contains odd numbers sorted in descending order, rest portion contains even numbers sorted in ascending order. GFG
Algo:
1. Need to move all even and odd numbers on respective sides. Then sort these part individually. Array.sort in Java also takes start and end position for sorting.
Arrays.sort(arr, start , end) -> start and end both inclusive.
If we first sort and then move sorting might be affected.

25. ** Given an array of both positive and negative integers ‘arr[]’ which are sorted. Task is to sort square of the numbers of the array. GFG
Algo:
1. When we square the array element half of them will be sorted in ascending order and half in descending order. The basic idea is that when we have two sorted arrays and we need to merge them to produce a sorted result, we can do that in O(n) times. Efficient solution is based on the fact that given array is already sorted. We do following two steps.

1. Divide the array into two part “Negative and positive “.
2. Use merge function to merge two sorted arrays into a single sorted array.

Time complexity: O(n)
space complexity: O(n)
2. Simple solution is to first convert each array elements into its square and than apply any “O(nlogn)” sorting algorithm to sort the array elements.
Time complexity : O(n log n)
*** Similar:  Given an integer array of which both first half and second half are sorted. Task is to merge two sorted halves of array into single sorted array. GFG

26. *** Given an array of distinct elements. The task is to find triplets in array whose sum is zero. GFG
Algo:
1. Brute Force, O(n3)
2. Sorting – Fix an element in the array and then for the rest of the array use two pointer problem logic to find two numbers whose sum negative of the fixed value.
We reduce our problem to a 2 sum problem.
Time Complexity : O(n2)
Auxiliary Space : O(1)
3. Hashing – Fix an element in the array and then for the rest of the array use logic to find two numbers whose sum is negative of fixed value.
Time Complexity : O(n2)
Auxiliary Space : O(n)

27. *** Check if reversing a sub array make the array sorted – Given an array of distinct n integers. The task is to check whether reversing one sub-array make the array sorted or not. If the array is already sorted or by reversing a subarray once make it sorted, print “Yes”, else print “No”. GFG
Algo:
1. Sorting

The idea is to compare the given array with the sorted array. Make a copy of the given array and sort it. Now, find the first index(front) and last index(end) which do not match with sorted array.  Now check the elements between front and end – they should be sorted in the opposite order.
Time Complexity: O(nlogn).
2.  Observe, answer will be “Yes” when the array is sorted or when the array consist of three parts. First part is increasing subarray, then decreasing subarray and then again increasing subarray. So, we need to check that array contain increasing elements then some decreasing elements and then increasing elements. In all other case, answer will be “No”.
Time Complexity: O(n).
Do not mix the above question with this. Above is about reversing a sub-array and below is about sorting a subarray.
**** Similar: Given an unsorted array of integers, find the shortest subarray, which upon sorting will result in complete sorted array.  Code
Youtube Here we don’t need to sort the subarray but only return the index of the subarray to be sorted.
Start from left to right and find the out of position element – minInd
Start from right to left and find the out of position element – maxInd
Now find the minimum and max element within minInd and maxInd.
Now in the main array find the correct position of minInd and maxInd as this is the correct position of the element in the unsorted part which will have to be moved.  These two new index will be our solution.

28. ** Given an array of integers, we need to find out whether it is possible to construct at least one non-degenerate triangle using array values as its sides. In other words, we need to find out 3 such array indices which can become sides of a non-degenerate triangle. GFG
Algo: See the condition to form a non-degenerate triangle. A+b > C. So if we sort and then compare the pair in set of 3(like a sliding window problem) then it will work.
Why only 3 consecutive pair will work ??
Let we are at index i and 3 line segments are arr[i], arr[i + 1] and arr[i + 2] with relation arr[i] < arr[i+1] < arr[i+2], If they can’t form a non-degenerate triangle, Line segments of lengths arr[i-1], arr[i+1] and arr[i+2] or arr[i], arr[i+1] and arr[i+3] can’t form a non-degenerate triangle also because sum of arr[i-1] and arr[i+1] will be even less than sum of arr[i] and arr[i+1] in first case and sum of arr[i] and arr[i+1] must be less than arr[i+3] in second case, So we don’t need to try all the combinations, we will try just 3 consecutive indices of array in sorted form.
The total complexity of below solution is O(n log n)