Puzzle: Find the order of n persons standing in a line (based on their heights)

Question

Saw this question on Careercup.com:

Given heights of n persons standing in a line and a list of numbers corresponding to each person (p) that gives the number of persons who are taller than p and standing in front of p. For example,

Heights: 5 3 2 6 1 4

InFronts:0 1 2 0 3 2

Means that the actual actual order is: 5 3 2 1 6 4

The question gets the two lists of Heights and InFronts, and should generate the order standing in line.

My solution:

It could be solved by first sorting the list in descending order. Obviously, to sort, we need to define an object Person (with two attributes of Height and InFront) and then sort Persons based on their height. Then, I would use two stacks, a main stack and a temp one, to build up the order.

Starting from the tallest, put it in the main stack. If the next person had an InFront value of greater than the person on top of the stack, that means the new person should be added before the person on top. Therefore, we need to pop persons from the main stack, insert the new person, and then return the persons popped out in the first step (back to the main stack from temp one). I would use a temp stack to keep the order of the popped out persons. But how many should be popped out? Since the list is sorted, we need to pop exactly the number of persons in front of the new person, i.e. corresponding InFront.

I think this solution works. But the worst case order would be O(n^2) -- when putting a person in place needs popping out all previous ones.

Is there any other solutions? possibly in O(n)?

Answer 1

The O(nlogn) algoritm is possible.

First assume that all heights are different.

Sort people by heights. Then iterate from shortest to tallest. In each step you need an efficient way to put the next person to the correct position. Notice that people we've already placed are not taller that 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. This task can be done using a data structure called interval tree in O(logn) time. So the total time of an algorithm is O(nlogn).

This algorithm works well in case where there's no ties. As it may be safely assumed that empty places up to front will be filled by taller people.

In case when ties are possible, we need to assure that people of the same height are placed in increasing order of their positions. It can be achieved if we will process people by non-decreasing inFronts value. So, in case of possible ties we should also consider inFronts values when sorting people.

And if at some step we can't find a position for next person then the answer it "it's impossible to satisfy problem constraints".