Sort an Array According to the Relative Order of Another Array

Moderate
0/80
Average time to solve is 30m
Contributed by
1 upvote

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 )
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
``````
Console