New update is available. Click here to update.

Last Updated: 17 Feb, 2021

Ninja

```
1. Consider that all elements in array βHeightβ are unique.
2. It is guaranteed that a valid order always exists for the given array βHeightβ and βInfrontβ.
```

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

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

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

Approaches

There are βNβ people in a queue, so they can stand in N! ways in a queue. We one by one check for all of the permutations whether it is an actual order of people in a queue or not.

We can one by one generate all the permutations using the **nextPermuation** method as described below.

- Create a function
**nextPermution(permutation, N)**that finds the next permutation of a given array '**permutation**β of size β**nβ.**In this function, we do the following.**Start iterating the array from backward and find an index βiβ such that permutation[i] < permutation[i+1]. Return false, if such an index doesnβt exist.****Find an index βjβ such that permutation[j] is the smallest integer in the suffix starting from βiβ for which condition permutation[j] > permutation[i] holds true.****Swap permutation[i] with permutation[j].**- Reverse suffix starting from
**βiβ.** **Return true as it indicates the next permutation exists. Note, in this approach, we have modified the given permutation to its lexicographically next permutation.**

**Algorithm**

- Create an array β
**permutationβ**of size β**N**β such that**permutation[i]:= i.** - Use method
**nextPermution(permutation, N)**to one by generating all permutations of the array β**permutationβ**for each permutation we will do the following.- Initialize a boolean variable
**flag:= true**. - Run a loop where β
**iβ**ranges from**β0β to βN-1β.****Initialize an integer variable βtallerBeforeβ:= 0**- Run a loop where
**βj**β ranges from**β0β to βi-1β:**- If
**height[permutation[j]] > height[permutation[i]],**increment**tallerBefore**by one.

- If
- If
**tallerBefore != Infront[permuation[i]]**, assign**flag := false**and break this loop.

- If
**flag = true,**Create an integer array β**result**β of size βNβ such that**result[i] = height[permuation[i]]**and then return this array**result**.

- Initialize a boolean variable

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.

- Initialize an integer variable
**Return βresultβ.**

We can optimize the previous approach by using Segment Tree which is a data structure used to optimize range queries. In our problem, we need to efficiently find the **kth **empty slot.

To do that, we can build a segment tree, such that each of its nodes gives the number of empty slots in a particular range. Generally, we represent segment tree by an array, Here we will represent segment tree by array named as β**tree**β. In this array **tree[0] **will be the root of segment tree that will give the number of empty slots in the range** [0, N-1]**, **tree[1] **will be left child of the root, that will give the number of empty slots in the range** [0, (N-1)/2]**,** tree[2]** will be the right child of the root, that will give the number of empty slots in the range **[(N-1)/2+1, N-1]**. In general, for any node represented by a **tree[i]** and gives the number of the empty slot in the range **[l, r]**, its left child is represented by a **tree[2*i+1]**, which gives the number of empty slots in a range** [l, (l+r)/2]** and its right child is represented by a **tree[2*i+2]**, which gives the number of empty slots in a range** [(l+r)/2+1, r].**

Now, we can use this segment tree to find kth empty slot efficiently, to do this we start from the root node and in each step check whether the desired empty exists in the range represented by its left node or right node.

**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. - Create an array
**tree**of size 4*N. It will represent our desire segment tree. - Build this segtree by keeping value of all leaf node 1(containing 1 empty slot), and for any internal node βiβ
**tree[i] = tree[2*i+1] + tree[2*i+2]**, i.e sum of its left and right child node. - 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 -;
- Recursively find the
**(infront[i] + 1)th**empty slot using segtree and update segree accordingly. - This can be done by calling a recursive function
**findEmptySlot(tree, root, left, right, k)**where**tree**represents segment tree,**root**is the current root of segment tree, and we need to find Kth empty slot in the range [left, right] (range represent by root). We will call this function as**findEmptySlot(tree, 0, 0, N-1, infront[i] + 1).**And in each recursive step do the following steps -:- Decrement
**tree[root]**by 1, as one slot in the range given by**root,**will be occupied. - If
**left == right**, i.e we are at a leaf node, then**return left**as it will be our desired empty slot. - if
**tree[2*root+1] >= K**, i.e its left child has more than K empty slot, then recur in left subtree i.e**findEmptySlot(tree, 2*root+1, left, (left+right)/2, K),**otherwise recur in right subtree i.e call**findEmptySlot(tree, 2*root+2, (left+right)/2+1, right, K-tree[2*root+1]).**Note that the Kth empty slot in range represented by root will be**(K - tree[2*root+1])th**empty slot in range represented by right node**.**

- Decrement
- Assign value return by this recursive function to
**result[i].**

- Recursively find the
**Return βresultβ.**