By Long Luo

This article is the solution Pattern of Data Pairs Problem: Sorting First then Greedy of Problem 406. Queue Reconstruction by Height.

Intuition

The Data Pair \(\textit{people}[h, k]\), \(h_i\) represents the i-th person of height \(h_i\), \(k_i\) represents the other people in front who have a height greater than or equal to \(h_i\).

Pattern:

When face such kind of problem with Data Pair, sorting first will simplify the problem.

Usually, we will sort the first element in ascending order, while the second element in descending order, or sort the first element in descending order with the second element in ascending order.

Greedy

We sort the \(\textit{people}\) pairs first by \(height\) in descending order, and \(k\) in ascending order.

According to the descending order of \(height\), for each person, the number of people before him is the number of people whose height is greater than or equal to him.

According to the ascending order of \(k\), because the \(k\) is increase later, which can reduce the number of insert operations.

Take the example:

After sorting:

1

[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]

Insert one by one:

1
2
3
4
5
6

[7,0]
[7,0], [7,1]
[7,0], [6,1], [7,1]
[5,0], [7,0], [6,1], [7,1]
[5,0], [7,0], [5,2], [6,1], [7,1]
[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]

The code is as follows:

1
2
3
4
5
6
7
8
9
10

public int[][] reconstructQueue(int[][] people) {
    Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);

    LinkedList<int[]> ans = new LinkedList<>();
    for (int[] person : people) {
        ans.add(person[1], person);
    }

    return ans.toArray(new int[ans.size()][]);
}

Analysis

• Time Complexity: \(O(nlogn)\).
• Space Complexity: \(O(logn)\).

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗