This is a classic problem. The solution is easy but heuristic.

Firstly, we can attach the code here.

Leetcode406

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | class Solution { public int[][] reconstructQueue(int[][] people) { if (people == null || people.length == 0 || people[0].length == 0) { return people; } Arrays.sort(people, (a, b)->a[0]==b[0]?a[1]-b[1]:b[0]-a[0]); List<int[]> temp = new ArrayList<>(); for (int[] pp : people) { temp.add(pp[1], pp); } int[][] res = new int[people.length][2]; for (int i = 0; i < people.length; i++) { res[i][0] = temp.get(i)[0]; res[i][1] = temp.get(i)[1]; } return res; } } |

Time complexity: O(n^2) Space Complexity: O(n)

This is not the best one, which the best time complexity can be achieved by BST.

## Algorithm Analysis

We can easily know that for the shortest one standing backmost, pair[1] is his correct location in the final answer. In other words, there is no relationship between this person and others.

We can eliminate this person and the problem of n people is converted to subproblem of (n-1) people. And another step is to insert this person based on his pair[1].

Based on this way, we can compress the problem until only one person. It is easy to implement in this way.