Order of People Heights

Posted: 17 Feb, 2021
Difficulty: Ninja

PROBLEM STATEMENT

Try Problem

There are ‘N’ people numbered from 0 to N - 1, standing in a queue. You are given two arrays ‘Height’ and ‘Infront‘ consisting of ‘N’ non-negative integers. ‘Height[i]’ gives the height of the ith person, and ‘Infront[i]’ gives the number of persons who are taller than the ith person and standing in front of the ith person.

Your task is to find out the actual order of people in a queue. You should 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.

Note :

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

Example :

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’.
Input format :
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’.
Output format :
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.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
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
Approach 1

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

  1. Create an array ‘permutation’ of size ‘N’ such that permutation[i]:= i.
  2. 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 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 .
Try Problem