Sorting – Set 2

Sorting Set 1  Sorting Set 3 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. We can just take the diff of first two and check if all follow the same diff.


  2. Find pair with greatest product in array 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:  Now the maximum product solution will be never be greater than the maximum element in the array ( we need a,b,c such that a*b = c and all three should be present in the given array).  
    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: Based on the observation we can conclude that the diff will be minimum when the values are contiguous. If we pick any random larger value then the difference will be high.
    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”. GFGAlgo: Sort both the array and use two pointers at the starting. Simple
  5. Chocolate Distribution Problem. GFG

    Algo: 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: As 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.


  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: Start printing element fron n/2 till the end of array.


  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
    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. [Pending] *** Count Inversions in an array (Using Merge Sort).  GFG
    Algo:


  12. 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.


  13. 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.


  14. Maximum product of a triplet (subsequnece of size 3) in array 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


  15. Given an unsorted array, find the minimum difference between any pair in given array. GFG. Asked in Amazon
    Algo: Sort the array. The minimum difference will be from any two adjacent element.  Complexity – O(n Log n)


  16. 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: The idea is to traverse from rightmost side and find the first out of order element (element which is smaller than previous element). Once first element is found, find the other our of order element by traversing the array toward left side.


  17. 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.


  18. **** 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}.


  19. 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


  20. **** 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[].



  21. Count all distinct pairs with difference equal to k 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.
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