Sort an Array According to the Relative Order of Another Array

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
1 upvote
Asked in company
Snapdeal

Problem statement

You are given two arrays, ‘P’ and ‘Q’ of length ‘N’ and ‘M’, sort ‘P’ so that the relative order of the elements is the same as it is in ‘Q’. Append the elements that are missing from ‘Q’ at last, sorted in non-decreasing order.

Note: If elements are repeated in the second array, consider their first occurrence only.

Example: 
Input: ‘N’ = 5, ‘M’ = 3,  ‘P’ = {1, 2, 4, 5, 3} ‘Q’ = {2, 1, 3}.

Output: {2, 1, 3, 4, 5}.

Since the array ‘P’ should be sorted such that the relative order of ‘Q’  is maintained so, 2 comes before 1 in ‘P’, then 1 comes before 3 and after 2 and then 3 comes before 1 and 2. Finally, all the remaining elements are appended at last in sorted order.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains an integer ‘N’ and ‘M’ denoting the length of the array ‘P’ and array ‘Q’. 

The second line of each test case contains ‘N’ space-separated integers.

The third line of each test case contains ‘M’ space-separated integers.
Output format : 
For each test case, you don’t need to print anything just rearrange the array ‘P’.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^5
1 <= M <= 10^5

Sum of N Over all the Test cases <= 10^5
Sum of M Over all the Test cases <= 10^5

Time Limit: 1 sec
Sample Input 1 :
2
11 4
20 10 20 50 70 10 90 30 60 80 80
20 10 80 30
11 4
20 10 20 50 70 10 90 30 60 80 80 
99 22 444 56
Sample Output 1 :
20 20 10 10 80 80 30 50 60 70 90
10 10 20 20 30 50 60 70 80 80 90
Explanation Of Sample Input 1 :
For the first case:
Since the array ‘P’ should be sorted such that the relative order of ‘Q’  is maintained so, 20, 10, 80, and 30 are placed before then all the elements are appended at last in sorted order.


For the second case:
92, 22, 444, and 56 are not present in array ‘P’ so all the elements are appending in non-decreasing order.
Sample Input 2 :
2
4 2
10 12 7 19
1 12
5 3
19 17 12 11 1
1 2 3
Sample Output 2 :
12 7 10 19
1 11 12 17 19
Hint

Can you think of a way to solve this problem using binary search?

Approaches (2)
Binary Search

In this approach, examine the elements of array 2 to see if they appear in array 1. To find the elements, use a binary search. If elements from array 2 are located in array 1, print them. In the end, print all of the remaining elements from array 1.


 

The steps are as follows:-

Function sortAccording( [ int ] P, [ int ] Q, int n, int m):

  1. Let ‘P’ have a size of ‘N, and ‘Q’ has a size of ‘N’.
  2. Copy the contents of ‘P’ to a temporary array of size ‘N’ called ‘TEMP’.
  3. Create a new array called ‘VISITED’ and set all of its entries to false. The array visited[] is used to indicate which elements in ‘TEMP’are copied to ‘P’.
  4. Sort the array ‘TEMP’ in non-decreasing order.
  5. Set the output index ‘IND’ to zero.
  6. For each element of ‘Q[ i ]’ in ‘Q’do the following:
    1. If there are any occurrences of ‘Q[ i ]’ in ‘TEMP’, then binary search for all occurrences of ‘Q[ i ]’ in ‘TEMP’, copy all occurrences to ‘P[ IND ]’, and increment ‘IND’. Also, make a note of the copied elements that have been ‘VISITED’
    2. Copy all elements from ‘TEMP’ to ‘P’ that have not been visited.
Time Complexity

O( M * Log( M )+ N * log( M ) ), Where ‘N’ and ‘M’ are the length of the arrays ‘P’ and ‘Q’ respectively.

 

The sorting Algorithm takes O(M * log M) time to complete. O(N * log M) time is required for the combined operation of binary search along with copying and remembering the copied elements. As a result, the overall complexity is O(M Log M + N log M).

Hence the time complexity is  O(M * Log M + N * log M).

Space Complexity

O( N ), where ‘N’ is the length of the array ‘P’.

 

The space complexity of the above algorithm is O(N). Since we are using a temporary array to copy the elements of our given array.

Hence space complexity is O( N ).

Code Solution
(100% EXP penalty)
Sort an Array According to the Relative Order of Another Array
Full screen
Console