The idea:

- Find the person with 0 people in front of them. If you have 2 such people choose the shorter person
- For all the remaining people, subtract 1 from the number of people in front of them if the person chosen in step 1 is of greater or equal height. ([5,0] is the first person so for all people with height upto 5 we reduce people in front by 1)
- Go to step 1 (in every step we will have some one with zero people in front of them as we are subtracting)

Extra 1d array used to store number of people in front a person. This is decremented every time someone with height >= person's height is chosen in step 1

Can we reduce time with this approach?

```
import java.util.*;
public class Solution {
public int[][] reconstructQueue(int[][] people) {
int m = people.length;
if(m<2)
return people;
int n = people[0].length;
int A[] = new int[m];
int index=0;
int temp1, temp2;
for(int i=0; i<m; i++)
A[i]=people[i][1];
for(int i=0; i<m; i++){
index = -1;
for(int j=i; j<m; j++){
if(i>0){
if(people[j][0]<=people[i-1][0])
A[j]--;
}
if(A[j]==0){
if(index==-1)
index = j;
else{
if(people[j][0]<people[index][0])
index = j;
}
}
}
//Swap i and index
temp1 = people[index][0];
temp2 = people[index][1];
people[index][0] = people[i][0];
people[index][1] = people[i][1];
people[i][0] = temp1;
people[i][1] = temp2;
//Swap i and indes in A
temp1 = A[index];
A[index] = A[i];
A[i] = temp1;
}
return people;
}
}
```