# Relative Sorting

Posted: 21 Dec, 2020

Difficulty: Moderate

#### Given two arrays ‘ARR’ and ‘BRR’ of size ‘N’ and ‘M’ respectively. Your task is to sort the elements of ‘ARR’ in such a way that the relative order among the elements will be the same as those are in ‘BRR’. For the elements not present in ‘BRR’, append them in the last in sorted order.

#### For example

```
Consider the arrays as ARR = { 9, 5, 8, 4, 6, 5 } and BRR = { 8, 4, 5 }
The output for the above example is { 8, 4, 5, 5, 6, 9 }.
```

#### Note:

```
Elements of ‘BRR’ are non repeating.
```

##### Input Format:

```
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the ‘T’ test cases follow.
The first line of each test case or query contains two single-space separated integers 'N' and ‘M’ representing the size of the ‘ARR’ and ‘BRR’ respectively.
The second line contains 'N' single space-separated integers, representing the elements of array ‘ARR’.
The third line contains 'M' single space-separated integers, representing the elements of array ‘BRR’.
```

##### Output format:

```
For each test case, print ‘N’ single space-separated integers, representing the elements of ‘ARR’ after the required sorting order in a single line.
Print the output of each test case in a separate line.
```

##### Note:

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

##### Constraints:

```
1 <= T <= 5
1 <= N <= 10 ^ 5
1 <= M <= 10 ^ 5
(-10 ^ 9) <= ARR[i] , BRR[i] <= (10 ^ 9)
Time limit: 1 sec
```

Approach 1

- The idea is to maintain a
**visited**array of size N. - Now, look for all occurrences of BRR elements one by one in ARR and mark them as visited and add them in ans array.
- After performing the above operation. Insert all unvisited elements of ARR into a
**set**, if any. So that they get arranged in a sorted manner. - And then finally insert elements of the set into our RES array.

Approach 2

- The idea is to use sorting to reduce the search time for BRR elements in the ARR.
- Maintain a
**visited**array of size N, to keep track of the elements included in our ans array. - For each element of the BRR find the index
**firstIndex**of its first occurrence in the ARR using binary search and then iteratively count the occurrence of that elements and mark them visited. - Insert all unvisited elements of the ARR into our ans array.

Approach 3

- The idea is to maintain a map
**frequencyMap**of the elements ARR, for finding the count of occurrences of BRR elements in ARR. - Then, for each element of BRR, find its frequency by looking in
**frequencyMap**. Say for any element B its frequency comes out to be A, then add B, A times in the RES array. Also erase the entry corresponding to B from the**frequencyMap.** - After the above step, the
**frequencyMap**contains those elements whose corresponding elements do not lie in BRR. As the map contains elements in sorted order. So we simply iterate the rest of**frequencyMap**elements, and add them, its frequency times in our RES array.

SIMILAR PROBLEMS

# Lexicographic Permutation Rank

Posted: 13 Jul, 2021

Difficulty: Moderate

# Zero Pair Sum

Posted: 22 Jul, 2021

Difficulty: Moderate

# Implement a Queue

Posted: 27 Jul, 2021

Difficulty: Easy

# Remove K Corner Elements

Posted: 31 Jul, 2021

Difficulty: Easy

# Connecting Ropes

Posted: 12 Nov, 2021

Difficulty: Hard