Sorting – Set 2

Sorting Set 1  Sorting Set 3 
We have algo for finding the largest and second largest and all. Like we can sort the array and take the last element O(nlog(n)). Or use quick select on unsorted array, but that has worst case O(n^2) complexity. So before such answer consider the situation that simple cases like largest or second-largest can be done in O(n) time simply. Check Q14/Q15.
In sorting problem it’s common to see problem that can use binary search. So instead of using hash directly consider binary search.

Screen Shot 2017-06-25 at 6.57.43 PM

  1. Given an array of n integers. The task is to check whether an arithmetic progression can be formed using all the given elements. If possible print “Yes”, else print “No”. GFG
    Algo:   We don’t really need to know the arithmetic difference. Sort the array. We can just take the diff of first two and check if all follow the same diff.


  2. Given an array of n elements, the task is to find the greatest number such that it is product of two elements of given array. If no such element exists, print -1. Elements are within the range of 1 to 10^5.  GFG
    Algo:  Store all the numbers in an Map. Now sort the given array and traverse it from the end. For each number generate all it’s factor( complexity – O(sqrt(n))).
    For each pair of factor generated check if those number are present in Map. Will have to handle the case where both factor are same. Then we will have to check the frequency also( like for 100, factors are 10 * 10, so 10 should be present twice in  the map).
    – We sort the array and save all the array element in the hash map.
    – We start with the last element in the sorted array(since we are looking for the largest) and keep checking for each number to find such a combination. Then start checking if there are any two number that divide the largest number completely from the starting. If yes, result = last / first. result should also be present in the array, so we lookup in the hash table. If found then return. Else check for the other numbers.


  3. Chose k array elements such that difference of maximum and minimum is minimized Given an array of n integers and a positive number k. We are allowed to take any k integers from the given array. The task is to find the minimum possible value of the difference between maximum and minimum of K numbers. GFG
    Algo: Sliding window concept. Based on the observation we can conclude that the diff will be minimum when the values are contiguous.
    The idea is to sort the array and choose k continuous integers. Why continuous?
    Let the chosen k integers be arr[0], arr[1],..arr[r], arr[r+x]…, arr[k-1], all in increasing order but not continuous in the sorted array. This means there exists an integer p which lies between arr[r] and arr[r+x],. So if p is included and arr[0] is removed, then the new difference will be arr[r] – arr[1] whereas old difference was arr[r] – arr[0]. And we know arr[0] <= arr[1] <= ..<= arr[k-1] so minimum difference reduces or remain same. If we perform same procedure for other p like number, we get the minimum difference


  4. Given two arrays of equal size n and an integer k. The task is to permute both arrays such that sum of their corresponding element is greater than or equal to k i.e a[i] + b[i] >= k. The task is print “Yes” if any such permutation exists, otherwise print “No”. GFG
    Algo:  The idea is to sort one array in ascending order and another array in descending order and if any index does not satisfy the condition a[i] + b[i] >= K then print “No”, else print “Yes”. If the condition fails on sorted arrays, then there exists no permutation of arrays which can satisfy the inequality. Check the proof on GFG.


  5. Chocolate Distribution Problem. GFG
    Algo: Sliding window. An efficient solution is based on the observation that, to minimize difference, we must choose consecutive elements from a sorted packets. We first sort the array arr[0..n-1], then find the subarray of size m with minimum difference between last and first elements.


  6. *** Given an array of integers which may contain duplicate elements, an element of this array is given to us, we need to tell the final position of this element in the array, if a stable sort algorithm is applied. GFG
    Algo: The position of an element in a sorted array is decided by only those elements which are smaller than given element. We count all array elements smaller than given element and for those elements which are equal to given element, elements occurring before given elements’ index will be included in count of smaller elements this will insure the stability of the result’s index.


  7. Given an array of n elements. The task is to find number of sextuplets that satisfy the below equation such that a, b, c, d, e and f belong to the given array….. GFG
    Algo: 
    1. Generate all possible values for RHS and store in a sorted array( use three nested loop and store using extra space and then sort it). Then generate the LHS in the same way as above and do a binary search for the LHS value calculated from the formula in the above sorted array.
    2. We can generate the RHS in the same manner as above and then store it in a hash table instead of a sorted array. Makes lookup faster.


  8. * Count minimum number of subsets (or subsequences) with consecutive numbers  – Given an array of distinct positive numbers, the task is to calculate the number of subsets (or subsequences) from the array such that each subset contains consecutive numbers. GFG 
    Algo: The idea is to sort the array and traverse the sorted array to count the number of such subsets. To count the number of such subsets, we need to count the consecutive numbers such that difference between them is not equal to one.
    Time Complexity : O(nlogn)
    This problem is similar to this. Here we need to find the longest sequence. It uses hashing to reduce the complexity. This can also be modified to achieve the same result.


  9. *** Given an array of n elements, the task is to find the elements that are greater than half of elements in an array. In case of of odd elements, we need to print elements larger than floor(n/2) elements where n is total number of elements in array.  GFG
    Algo:
    1. Sort the array and then loop through. Complexity – O(nlog(n)).
    2. We can use Quick Select to find the nth smallest element in O(n) time. SO. QuickSelect is a variation of QuickSort. We can use it to find the n/2 smallest element(which will be median) in O(n). Then using the median find the element larger than median in O(n) time. Overall Complexity O(n).


  10. *** Sort an array according to count of set bits – Given an array of positive integers, sort the array in decreasing order of count of set bits in binary representations of array elements. GFG.
    Algo:
    1. We can count the set bit an integer using Brian Kernighan’s Algorithm(O(log N)). Now we can define our own comparator to sort the array using a stable sorting algo. So overall complexity will be n(logN)*log(N) – as the comparator will have to calculate the bit count.
    2.There can be minimum 1 set-bit and only a maximum of 31set-bits in any integer.
    We take an array of 32 bits and map the element to corresponding position to each index. So like for index 2 we have 3,5. This will have to be maintained such that we have the order preserved. Now since we need the result in descending order, we start at the end this list and start printing element in the order.


  11. Given an array of digits (values are from 0 to 9), find the minimum possible sum of two numbers formed from digits of the array. All digits of given array must be used to form the two numbers. GFG
    Algo:  The idea is to sort the array in increasing order and build two numbers by alternating picking digits from the array. So first number is formed by digits present in odd positions in the array and second number is formed by digits from even positions in the array. Finally, we return the sum of first and second number.


  12. Given an array arr[0..n-1] of distinct elements and a range [low, high], find all numbers that are in range, but not in array. The missing elements should be printed in sorted order. GFG
    Algo:
    1. Use Sorting : Sort the array, then do binary search for ‘low’. Once location of low is find, start traversing array from that location and keep printing all missing numbers.
    2. Use Hashing : Create a hash table and insert all array items into the hash table. Once all items are in hash table, traverse through the range and print all missing elements.


  13. Given an integer array, find a maximum product of a triplet in array. GFG
    Algo:
    1. Sort the array and return the maximum of product of last three elements of the array and product of first two elements and last element.  
    O(nlogn) Time, O(1) Space 

    2. Scan the array and compute Maximum, second maximum and third maximum element present in the array. Scan the array and compute Minimum and second minimum element present in the array. Return the maximum of product of Maximum, second maximum and third maximum and product of Minimum, second minimum and Maximum element.
        O(n) Time, O(1) Space


  14. Given an unsorted array, find the minimum difference between any pair in given array. GFG. Asked in Amazon
    Algo:
    1. Sort the array. The minimum difference will be from any two adjacent element.  Complexity – O(n Log n)
    2. Can we find the second largest and largest using  quick select ??   The worst case time complexity of this method is O(n^2), but it works in O(n) on average. 


  15. Given an almost sorted array where only two elements are swapped, how to sort the array efficiently? Expected time complexity is O(n) and only one swap operation to fix the array. GFG
    Algo: Make two traversal – one form right and one from left. Find the two elements out of position. Swap those.


  16. An interval is represented as a combination of start time and end time. Given a set of intervals, check if any two intervals overlap. GFG
    Algo:
    1) Sort all intervals in increasing order of start time. This step takes O(nLogn) time. 2) In the sorted array, if start time of an interval is less than end of previous interval, then there is an overlap. This step takes O(n) time.


  17. **** Sort an array in wave form – Given an unsorted array of integers, sort the array into a wave like array. An array ‘arr[0..n-1]’ is sorted in wave form if arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= …..  GFG
    Algo:  A Simple Solution is to use sorting. First sort the input array, then swap all adjacent elements. For example, let the input array be {3, 6, 5, 10, 7, 20}. After sorting, we get {3, 5, 6, 7, 10, 20}. After swapping adjacent elements, we get {5, 3, 7, 6, 20, 10}.


  18. Given a sorted array and a number x, find a pair in array whose sum is closest to x. GFG
    Algo: Sort and then two pointer logic. O(n). We will need to consider the absolute difference. Max value in Java = Integer.MAX_VALUE


  19. **** Sort an array according to the order defined by another array – Given two arrays A1[] and A2[], sort A1 in such a way that the relative order among the elements will be same as those are in A2. For the elements not present in A2, append them at last in sorted order. GFG
    Algo: Sometimes in place and simple sorting solution are not possible. We have to use extra space. We should think in this direction if low complexity solution don’t seem likely. 
    Let size of A1[] be m and size of A2[] be n.
    1) Create a temporary array temp of size m and copy contents of A1[] to it.
    2) Create another array visited[] and initialize all entries in it as false. visited[] is used to mark those elements in temp[] which are copied to A1[].
    3) Sort temp[]
    4) Initialize the output index ind as 0.
    5) Do following for every element of A2[i] in A2[]
    …..a) Binary search for all occurrences of A2[i] in temp[], if present then copy all occurrences to A1[ind] and increment ind. Also mark the copied elements visited[]
    6) Copy all unvisited elements from temp[] to A1[].



  20. Given an integer array and a positive integer k, count all distinct pairs with difference equal to k. GFG
    Algo: Sort the data. Then for each element do a binary search for a[i] + k.
    Since a smaller value will pair up with there larger pair in the starting we don’t need to worry about search for a[i] – k, at any point of time. Can also be handled via Hashing.
Advertisements

One thought on “Sorting – Set 2

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s