# [Google] Form a Queue Given Heights

### Question

There is an array of integers which represent heights of persons.

Given another array… Let’s call it count-array. It contain how many persons in front of him are greater than him in height.

Example:

``````Input(Count array): 0, 0, 2, 0
Output(原数组): 2, 3, 1, 4
``````

### Solution

This is naive solution from floor 29 of this thread:

Example:

``````count array
i C[0,0,2,0]   N[4, 3, 2, 1]
3 C[3] = 0     在N里面删除N[0]=4, N=[3, 2, 1],   Ans=[4]
2 C[2] = 2     在N里面删除N[2]=1, N=[3, 2],   Ans=[1, 4]
1 C[1] = 0     在N里面删除N[0]=3, N=[2],   Ans=[3, 1, 4]
0 C[0] = 0     在N里面删除N[0]=2, N=[], Ans=[2, 3, 1, 4]
``````

But there is a problm here, since removing item from list requires O(n), we will achieve O(n2) time. How do we optimize this?

The answer is BST with each node keeping track of how many nodes is on the left branch, and how many on right branch. For details of this type of TreeNode, refer to [CC150v5] 11.8 Get Rank in Stream of Integers.

The conclusion:

### Code

Naive approach, O(n2):

``````public int[] form(int peopleCount, int[] countArray) {
int len = peopleCount;
int[] heightQueue = new int[len];
List<Integer> list = new ArrayList<Integer>();
for (int i = peopleCount; i > 0; i--) {