Sort an Array According to the Relative Order of Another Array

Moderate

0/80

Average time to solve is 30m

Contributed by

1 upvote

Asked in company

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

Console