Order of People Heights

Given a positive number N denoting the number of People, an array ‘Heights‘ which contains the heights of N persons standing in a queue, and an array ‘Infronts‘ whose each entry gives the number of persons who are taller than him and standing in front of him in the queue, return the list of actual order of every person’s height.

Examples:

Input :
N=6
Heights= 5 3 2 6 1 4 
Infronts= 0 1 2 0 3 2
Output :
5 3 2 1 6 4

Explanation:
The first person has height 5 and the number of people taller and in front of him is 0, which means he will be first in the actual ordering.
Similarly, Person of height 2 has 2 people taller and in front of him, which is why 5 and 3 are in front of him in the actual ordering.

Input :
N=3
Heights= 1 2 3
Infronts= 2 1 0
Output :
3 2 1

A Naive but extremely inefficient approach would be to try out all possible permutations of the given heights and verify if the ‘Infronts‘ numbers match for the given permutation. Time Complexity of this method is O(N!). A slightly better approach is to sort people by heights. Then iterate from shortest to tallest. In each step, you need an efficient way to put the next person into the correct position.

Notice that people we have 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 a place such that the number of empty positions in the front is equal to the ‘Infronts‘ value of this person.

Using the above method, we try to solve this problem is by using a Segment Tree/Interval Tree.
The root contains the number of elements in [0..N]. Left Node contains the number of elements in [0..N/2].
Right Node contains the number of elements in [(N/2)+1 ..N]. If we need to find the i’th empty position, we look at the number of elements in [0..N/2].

Let’s call this number ‘X‘. If (N/2)-X >=i , the empty position lies on the left part of the array so we move down to the left node. Else, we look for i-((N/2)-X)th position in the right part of the array and also move down the right node in the segment tree.

Implementation in C++:

#include <bits/stdc++.h>
using namespace std;

// Function to find empty space in the segment tree
int empty_pos(vector<int> &tree, int pos) 
{
    int n = tree.size() / 2, i = 0;
    while (i < n - 1) 
    {
        --tree[i];
        if (tree[2 * i + 1] > pos)
            i = 2 * i + 1;
        else 
        {
            pos -= tree[2 * i + 1];
            i = 2 * i + 2;
        }
    }
    --tree[i];
    return i - (n - 1);
}

// Function to build the segment tree
vector<int> build_segment_tree(int len) 
{
    int n = pow(2, ceil(log2(len)));
    vector<int> tree(2 * n);
    for (int i = 0; i <= len - 1; ++i)
        tree[n - 1 + i] = 1;
    for (int i = n - 2; i >= 0; --i)
        tree[i] = tree[2 * i + 1] + tree[2 * i + 2];
    return tree;
}

// Utility function to print the final solution
void print_vector(vector<int> v) 
{
    for (int i = 0; i < v.size(); ++i)
        cout << v[i] << " ";
    cout << endl;
}

vector<int> order(vector<int> &heights, vector<int> &infronts) 
{
    vector<int> permutation(heights.size());
    for (int i = 0; i < permutation.size(); ++i)
        permutation[i] = i;
        
    sort(permutation.begin(), permutation.end(), [&](const int a, const int b) { return (heights[a] < heights[b]); });
    
    vector<int> tree = build_segment_tree(heights.size());
    vector<int> res(heights.size(), -1);
    for (int i = 0; i < permutation.size(); ++i)
        res[empty_pos(tree, infronts[permutation[i]])] = heights[permutation[i]];
    return res;
}

int main()
{
    int N = 6;
    vector<int> heights = {5, 3, 2, 6, 1, 4};
    vector<int> infronts = {0, 1, 2, 0, 3, 2};
    vector<int> solution = order(heights, infronts);
    for (int i = 0; i < N; i++)
    {
        cout << solution[i] << " ";
    }
    return 0;
}

Output:

5 3 2 1 6 4

Time Complexity: O(Nlog(N))
Space Complexity: O(N)