Order of People Heights — Asked in Flipkart and Google Interviews

Problem Statement :

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.

Given:

6
5 3 2 6 1 4
0 1 2 0 3 2

Output :

5 3 2 1 6 4

Explanation of given Test Cases :

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

Approach :

Segment Tree

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

1. 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.
2. Create an array tree of size 4*N. It will represent our desire segment tree.
3. 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.
4. Create an array ‘result’ of size ’N’ and fill it with 0.
5. 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.
• Assign value return by this recursive function to result[i].

Return ‘result’.

Time Complexity : O(N*log(N))
Space Complexity : O(N)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.