Last Updated: 30 Jul, 2022
Sort an Array According to the Relative Order of Another Array
Moderate
Asked in company
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.
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
Approaches
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):
- Let ‘P’ have a size of ‘N, and ‘Q’ has a size of ‘N’.
- Copy the contents of ‘P’ to a temporary array of size ‘N’ called ‘TEMP’.
- 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’.
- Sort the array ‘TEMP’ in non-decreasing order.
- Set the output index ‘IND’ to zero.
- For each element of ‘Q[ i ]’ in ‘Q’do the following:
- 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’
- Copy all elements from ‘TEMP’ to ‘P’ that have not been visited.
In this approach, the goal is to keep track of the frequency of each element of the first array in a hash table.
The steps are as follows:-
Function sortAccording( [ int ] P, [ int ] Q, int n, int m):
- Check whether or not each element of the second array is present on the map.
- Print the element ‘X’ times if it appears on the map, where ‘X’ is the frequency of that element in the first array.
- We also remove that element from the map, leaving only the elements in the first array that are present (but not present in the second array).
- They must be sorted before being added at the end.
- Although keys in std::map or TreeMap are already ordered, the insertion and retrieval times are O(log(n)). We get O(1) insertion and retrieval time if we use std::unordered map or HashMap, but we'll have to sort because the keys aren't in any particular order.