Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

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.

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

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

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

```
20 20 10 10 80 80 30 50 60 70 90
10 10 20 20 30 50 60 70 80 80 90
```

```
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.
```

```
2
4 2
10 12 7 19
1 12
5 3
19 17 12 11 1
1 2 3
```

```
12 7 10 19
1 11 12 17 19
```