# O(n^2) solution with O(n) extra space

• The idea:

1. Find the person with 0 people in front of them. If you have 2 such people choose the shorter person
2. 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)
3. 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;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.