Java solution using Arrays.sort() and "insert sorting" idea

• We first sort the people to make them stand from the highest to shortest. For people with same height, sort them according to the count of people before them from small to big.

Then, we use the way similar to insert sorting to reorder the people. For a given person to insert, all the people already sorted are higher, so we just insert him in the "right" place to make the people before him as his "count" indicates. Since he is shorter than all the people in the sorted list, the "count" of the "existing" people does not be broken by the insertion.

``````    public int[][] reconstructQueue(int[][] people) {
if (people == null || people.length == 0 || people[0].length == 0)
return new int[0][0];

Arrays.sort(people, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
if (b[0] == a[0]) return a[1] - b[1];
return b[0] - a[0];
}
});

int n = people.length;
ArrayList<int[]> tmp = new ArrayList<>();
for (int i = 0; i < n; i++)

int[][] res = new int[people.length][2];
int i = 0;
for (int[] k : tmp) {
res[i][0] = k[0];
res[i++][1] = k[1];
}

return res;
}
``````

• Could you explain what the array.sort mean? What the a and b represent?

• @manvswilds learn about Comparator in Java

• OMG very genius idea and clean code! Thank you so much!

• I would like to replace if (people == null || people.length == 0 || people[0].length == 0) with if (people == null || people.length == 0 || people[0] ==null ||people[0].length == 0) because theoretically people can be{null} which has length of 1 but people[0] is null, other than that, very smart idea.

• Why not use `ArrayList.toArray(T[])` to convert the list to array?

• This post is deleted!

• genius idea, i need some times to take it.

• Love this explanation, thanks for sharing.

• How did you come up with this? Any theory to support this when you are thinking of this?

• @genius1wjc
Use Lambda

``````
class Solution {
public int[][] reconstructQueue(int[][] people) {
if (people == null || people.length == 0 || people[0].length == 0) {
return new int[0][0];
}
Arrays.sort(people, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]));
List<int[]> tmp = new ArrayList<>();
for (int i = 0; i < people.length; i++) {
}

return tmp.toArray(new int[people.length][]);

}
}

``````

• ``````class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (a, b) -> (b[0] == a[0] ? a[1] - b[1] : b[0] - a[0]));
List<int[]> res = new ArrayList<>();
for (int[] p : people) {