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)?

Solution 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".

Solution 2

There exists an algorithm with O(nlogn) average complexity, however worst case complexity is still O(n²).

To achieve this you can use a variation of a binary tree. The idea is, in this tree, each node corresponds to a person and each node keeps track of how many people are in front of him (which is the size of the left subtree) as nodes are inserted.

Start iterating the persons array in decreasing height order and insert each person into the tree starting from the root. Insertion is as follows:

1. Compare the frontCount of the person with the current node's (root at the beginning) value.
2. If it is smaller than it insert the node to the left with value 1. Increase the current node's value by 1.
3. Else, descend to the right by decreasing the person's frontCount by current node's value. This enables the node to be placed in the correct location.

After all nodes finished, an inorder traversal gives the correct order of people.

Let the code speak for itself:

public static void arrange(int[] heights, int[] frontCounts) {
  Person[] persons = new Person[heights.length];

  for (int i = 0; i < persons.length; i++)
    persons[i] = new Person(heights[i], frontCounts[i]);

  Arrays.sort(persons, (p1, p2) -> {
    return Integer.compare(p2.height, p1.height);
  });

  Node root = new Node(persons[0]);

  for (int i = 1; i < persons.length; i++) {
    insert(root, persons[i]);
  }

  inOrderPrint(root);
}


private static void insert(Node root, Person p) {
  insert(root, p, p.frontCount);
}

private static void insert(Node root, Person p, int value) {
  if (value < root.value) { // should insert to the left
    if (root.left == null) {
      root.left = new Node(p);
    } else {
      insert(root.left, p, value);
    }
    root.value++; // Increase the current node value while descending left!
  } else { // insert to the right
    if (root.right == null) {
      root.right = new Node(p);
    } else {
      insert(root.right, p, value - root.value);
    }
  }
}

private static void inOrderPrint(Node root) {
  if (root == null)
    return;

  inOrderPrint(root.left);

  System.out.print(root.person.height);

  inOrderPrint(root.right);
}

private static class Node {
  Node left, right;
  int value;
  public final Person person;

  public Node(Person person) {
    this.value = 1;
    this.person = person;
  }
}

private static class Person {
  public final int height;
  public final int frontCount;

  Person(int height, int frontCount) {
    this.height = height;
    this.frontCount = frontCount;
  }
}

public static void main(String[] args) {
  int[] heights = {5, 3, 2, 6, 1, 4};
  int[] frontCounts = {0, 1, 2, 0, 3, 2};

  arrange(heights, frontCounts);
}

Solution 3

I think one approach can be the following. Although it again seems to be O(n^2) at present.

Sort the Height array and corresponding 'p' array in ascending order of heights (in O(nlogn)). Pick the first element in the list. Put that element in the final array in the position given by the p index.

For example after sorting,
H - 1, 2, 3, 4, 5, 6
p - 3, 2, 1, 2, 0, 0.

1st element should go in position 3. Hence final array becomes:
---1--

2nd element shall go in position 2. Hence final array becomes:
--21--

3rd element should go in position 1. Hence final array becomes:
-321--

4th element shall go in position 2. This is the position among the empty ones. Hence final array becomes:
-321-4

5th element shall go in position 0. Hence final array becomes:
5321-4

6th element should go in position 0. Hence final array becomes:
532164

Solution 4

I think the approach indicated above is correct. However a critical piece missing in the solutions above are.
Infronts is the number of taller candidate before the current person. So after sorting the persons based on height(Ascending), when placing person 3 with infront=2, if person 1 and 2 was in front placed at 0, 1 position respectively, you need to discount their position and place 3 at position 4, I.E 2 taller candidates will take position 2,3.

As some indicated interval tree is the right structure. However a dynamic sized container, with available position will do the job.(code below)

struct Person{
    int h, ct;
    Person(int ht, int c){
        h = ht;
        ct = c;
    }
};

struct comp{
  bool operator()(const Person& lhs, const Person& rhs){
      return (lhs.h < rhs.h);
  }  
};

vector<int> heightOrder(vector<int> &heights, vector<int> &infronts) {

    if(heights.size() != infronts.size()){
        return {};
    }
    vector<int> result(infronts.size(), -1);
    vector<Person> persons;
    vector<int> countSet;
    for(int i= 0; i< heights.size(); i++){
       persons.emplace_back(Person(heights[i], infronts[i]));
       countSet.emplace_back(i);
       }
    sort(persons.begin(), persons.end(), comp());
    for(size_t i=0; i<persons.size(); i++){
        Person p = persons[i];
            if(countSet.size() > p.ct){
                int curr = countSet[p.ct];
                //cout << "the index to place height=" << p.h << " , is at pos=" <<  curr << endl; 
                result[curr] = p.h;
                countSet.erase(countSet.begin() + p.ct);
            }

        }
    return result;
}

View more solutions

Comments

[wxyz]

In the actual order (5 3 2 1 6 4), '1' has index 3 (0 based) and there are 3 in front of it, all higher than it, so it should have the value 3 in inFronts list, not 0.

[Abhishek Bansal]

@wxyz it has an index of 3. It is not 0. Compare the height list and infront's list.

[Yash]

Can you explain in more detail, how can we do this in O(nlogn) using the interval tree ?

[Evgeny Shavlyugin]

@Yash, In nodes of our interval tree we store the sum of elements on the interval. Start from the root. In each step we first look if the sum of the elements in left child is less than our value. If it's true, then the answer is in the left subtree. Otherwise - in the right subtree. In the last case subtract sum of the left subtree from current value. Apply this step until leaf node is reached.