Leetcode 406. Queue Reconstruction by Height

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.