Queue Reconstruction by Height

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

Example 1:

Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] Explanation: Person 0 has height 5 with no other people taller or the same height in front. Person 1 has height 7 with no other people taller or the same height in front. Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1. Person 3 has height 6 with one person taller or the same height in front, which is person 1. Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3. Person 5 has height 7 with one person taller or the same height in front, which is person 1. Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

Example 2:

Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]] Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

Constraints:

• 1 <= people.length <= 2000
• 0 <= hi <= 10^6
• 0 <= ki < people.length
• It is guaranteed that the queue can be reconstructed.

Approach: Sort + Insert by Index (Optimal Solution)

Algorithm

1. Sort people by height descending; when heights are equal, sort by k ascending
2. Use an empty list to build the result
3. For each person p = [h, k], insert p at index k in the list
4. Return the list as a 2D array

Key Insight

After sorting by descending height, all already-placed people are taller than or equal to the current person. So inserting the current person at index k puts exactly k taller-or-equal people in front of them. People with equal height are sorted by ascending k so that earlier equal-height people (with smaller k) are placed first and end up in front, keeping the count exact.

Time & Space Complexity

• Time Complexity: O(n²) - sorting is O(n log n) but each list insert at an arbitrary index is O(n), for n people
• Space Complexity: O(n) - the result list stores all n people

Java Implementation

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class QueueReconstructionByHeight {

    public int[][] reconstructQueue(int[][] people) {
        // Sort by height descending; when heights are equal, by k ascending
        Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);

        List<int[]> ans = new ArrayList<>(people.length);
        for (int[] p : people) {
            ans.add(p[1], p); // insert at index k
        }
        return ans.toArray(new int[ans.size()][]);
    }

    // Test method
    public static void main(String[] args) {
        QueueReconstructionByHeight sol = new QueueReconstructionByHeight();
        int[][] people = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
        int[][] result = sol.reconstructQueue(people);
        System.out.println(Arrays.deepToString(result));
        // Expected: [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]
    }
}

Example Walkthrough

For people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]:

1. Sort by height descending, k ascending: [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]
2. Insert [7,0] at index 0: [[7,0]]
3. Insert [7,1] at index 1: [[7,0],[7,1]]
4. Insert [6,1] at index 1: [[7,0],[6,1],[7,1]]
5. Insert [5,0] at index 0: [[5,0],[7,0],[6,1],[7,1]]
6. Insert [5,2] at index 2: [[5,0],[7,0],[5,2],[6,1],[7,1]]
7. Insert [4,4] at index 4: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

Key Insights

1. Descending Height Order: Processing tallest first guarantees every already-inserted person is taller or equal
2. Index Equals k: Inserting at index k places exactly k taller-or-equal people in front
3. Equal Height Tie-break: Sorting equal heights by ascending k preserves the correct relative order
4. Guaranteed Valid: The problem guarantees the queue can be reconstructed, so no conflict ever occurs

The sort-and-insert approach is the optimal solution, providing O(n²) time and O(n) space.