Order of People Heights

Let there are 6 people, their heights are given by array ‘Height’ : [5, 3, 2, 6, 1, 4], and the number of people in front of them is given by array ‘Infront’: [0, 1, 2, 0, 3, 2] Thus the actual order of people’s height in the queue will be [5, 3, 2, 1, 6, 4] In this order, the first person in a queue i.e a person with a height of 5, has no person in front of them who is taller than him. The second person in a queue i.e a person with a height of 3 has 1 person (person with height 5) in front of them who is taller than him. The third person in a queue i.e a person with a height of 2 has 2 people (people with height 5 and 3) in front of them who are taller than him. The fourth person in a queue i.e a person with a height of 1 has 3 people (people with height 5, 3, 2) in front of them who are taller than him. The fifth person in a queue i.e a person with a height of 6 has no person in front of them who is taller than him. The sixth person in a queue i.e a person with a height of 4 has 2 people (people with height 5, and 6) in front of them who are taller than him. We can observe this is the only possible order that is possible according to the array ‘Infront’.

The first line of input contains an integer ‘T’ denoting the number of test cases. The next 3 * 'T' lines represent the ‘T’ test cases. The first line of each test case consists of a single integer ‘N’ representing the number of people in a queue. The second line of each test case consists of ‘N’ space-separated integers representing the array ‘Height’. The third line of each test case consists of ‘N’ space-separated integers representing the array ‘Infront’.

For each test case, print ‘N’ integers where the ‘ith’ integer is the height of the person who should be at the ith position from the start of the queue. Print the output of each test case in a new line.

1 <= T <= 50 1 <= N <= 10^4 1 <= Height[i] <= 10^9 0 <= Infront[i] < ‘N’ Where ‘T’ is the total number of test cases, ‘N’ is the number of people in the queue, Height[i], and Infront[i] respectively are height and number of people in front of ith who are taller than him. Time limit: 1 sec

Test case 1: There is no person in front of any person who is taller than him, Thus all of them must be present in the queue in increasing order of their height. Test case 2: See the problem statement for an explanation.

Sorting

Sort people by heights. Then iterate from shortest to tallest. In each step, you need an efficient way to put the next person in the correct position. Notice that the people we’ve already placed are not taller than the current person. And the people we place after are taller than the current. So we have to find the first empty place such that the number of empty positions in front of it is equal to the Infront value of this person.

For example, let there are 3 people, with Height = [5, 3, 1] and Infront = [0, 0, 1], Thus after sorting in increasing order of height , we get, Height = [1, 3, 5] and Infront = [1, 0, 0].

Let there are three positions in a queue i.e _ _ _

So first we place the person with height 1, after 1 empty position, ie _ 1 _.

Then we place, the person with height 3, such that there are exactly 0 empty positions before it, i.e 3 1 _,

Then we place, the person with height 5, such that there are exactly 0 empty positions before it, i.e 3 1 5

Thus [3, 1, 5] will be our required answer.

Algorithm

Sort the array ‘Height’ in increasing order and arrange the elements of array ‘Infront’ such that ‘Height[i]’ and ‘Infront[i]’, represent height and infront value of the same person after sorting. This can be done by creating a matrix people[][] of size n*2 such that people[i][0] = Height[i], and people[i][1] = Infront[i], sort this matrix people[][], according to increasing order of its first column i.e height, and then assign Height[i] := people[i][0] and Infront[i] := people[i][1].
Create an array ‘result’ of size ‘N’ and fill it with 0.
Run a loop where ’i’ ranges from 0 to ‘N-1’ and in each step do the following -;
- Initialize an integer variable ‘countEmpty’ := 0
- Run a loop where ‘j’ ranges from 0 to ‘N-1’ and in each iteration, if result[i]:= 0 and countEmpty < Infront[i], then increment countEmpty by one, otherwise if result[i]:= 0 and countEmpty == Infront[i], assign result[j] := Height[i] and break this inner loop.
Return ‘result’.

Time Complexity

O(N^2), where ‘N’ is the number of people.

Time taken by sorting will be O(NlogN), and here for each position, it takes O(N) time in the worst case to decide which person should be there. As there are ‘N’ positions in the queue, the overall time complexity will be O(N^2 + NlogN) = O(N^2).

Space Complexity

O(N), where ‘N’ is the number of people.

The extra space is used by the array ‘result’ and matrix ‘people’, both of them have a size of the order of ‘N’. Thus overall space complexity will be O(N).

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation Of Sample Input 1 :

Sample Input 2 :

Sample Output 2 :