# Java O(N * logN) , detailed explain

• The idea is simple, first sort the array by rules:
Two people : a,b
if a[0] > b[0] then a<b;
if a[0] < b[0] then a>b;
if a[0] = b[0] then sort by people[1];
if a[1] > b[1] then a>b;
...

for example, input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
after sort:
[[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]

next step, put the people in a list at specified position. Iterate the sorted array, when we pick a people , the people before is higher or equal to that. So we just put it according to the position people[1];

Here is the code:

``````public class Solution {
public int[][] reconstructQueue(int[][] people) {
if(people.length == 0) return new int[][]{};

//sort
Arrays.sort(people,new mC());

//put in a list
for (int i =1;i<people.length;i++) {
}

//return result
Iterator iterator = list.iterator();
int i = 0;
while (iterator.hasNext()) {
people[i++] = (int[]) iterator.next();
}
return people;
}
class  mC implements Comparator<int[]> {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[0] > o2[0]) return -1;
else if (o1[0] < o2[0]) return 1;
else {
return o1[1] - o2[1];
}
}
};
}``````

• I think the complexity of 'list.add' will be O(N^2) in the worst cast, that's to say you insert the element at the first place every time.

• @merryChris Agree. Not only for worst case, even for average, it is also O(n^2)

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