Sorting – Set 1

Sorting Set 2  Sorting Set 3

  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: We first sort both the arrays and then compare each element of the first array with each element of the second array for the possible pair, if it’s possible to form a pair, we form the pair and move to check for the next possible pair for the next element of the first array.  This can be optimized to run in O(n) only (think on the line when we have two pointers and we need to find the sum, there we move the pointer depending on the sum, here we will need to move it on the basis of difference).


  3. ** Find shortest unique prefix for every word in a given list. GFG
    Algo: Use trie instead of Sorting.


  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.


  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
    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. Start traversing the sequence by storing it in an array. Check if the current string is equal to next string and delete if required.
    2. 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. [Pending] 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
    Algo: Find the number of factors of each number(this can be done in sqrt(n) time for each number). Then we store the number and number_of_factor together and then sort that. 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 .
    Algo: The concept is important here – we can merge two sorted array in O(n).
    1. Apply the given equation to every array element and then sort.Time complexity of O(n log n)
    2.  The equation given is parabolic. So the result of applying it to a sorted array will result in an array that will have a maximum/minimum with the sub-arrays to its left and right sorted.
    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-arrays
    Time 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:  We need to just swap the values if diff of a[i] – a[i+1] == 1. n we need to sure that the part before that array is sorted before swap, if that’s not true then no point swapping.
    If we traverse array from left to right and we make sure elements before an index i are sorted before we reach i, we must have maximum of arr[0..i-1] just before i. And this maximum must be either smaller than arr[i] or just one greater than arr[i]. In first case, we simply move ahead. In second case, we swap and move ahead.


  11. We are given an array of strings, we need to sort the array in increasing order of string lengths.  GFG
    Algo: We can override the default java sort method to work with length. Or we can do a simple sorting, where we compare the string length instead of values.


  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.


  13. Program to print an array in Pendulum Arrangement – Read full details on the page  GFG
    Algo: Sort the array and then rotate by using the extra space.


  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

  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

     

  16. **** Find the largest multiple of 3 from array of digits | Set 2 (In O(n) time and O(1) space). GFG

  17. Given an integer array with repeated elements, the task is to find sum of all distinct elements in array.
    Algo: 1. Sorting   2. hashing


  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

  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: We can solve this problem without iterating over all possible subsets by observing the fact that our result subset will always be consecutive, once we sort the given array. The reason is sorting brings value-wise close elements together.
  21. ** Given three inte­gers, print them in sorted order with­out using if condition.
    Algo: The important part here is to find the minimum value in an array using max function.


  22. [Pending] 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

     

  23. [Pending] *** 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:  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. [Pending] Recursive Insertion Sort

  25. 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: Need to move all even and odd numbers on respective sides. Then sort these part individually.


  26. *** 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. It’s a lot similar to question 9 on this page (or to this). 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


  27. 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
    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)


  28. ** 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”.
    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.
    If front >= end, either the array is sorted or there’s only such point of difference.
    If ron
    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 above 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


  29. ** 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: 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)
Advertisements

One thought on “Sorting – Set 1

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