[Medium] 406. 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 who have a height greater than or equal to hi in front of them.

Write an algorithm to reconstruct the queue.

Examples

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 one taller or equal in front of them.
Person 1 has height 7 with no one taller or equal in front of them.
Person 2 has height 5 with two people taller or equal in front of them.
Person 3 has height 6 with one person taller or equal in front of them.
Person 4 has height 4 with four people taller or equal in front of them.
Person 5 has height 7 with one person taller or equal in front of them.

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]]
Explanation:
Person 0 has height 4 with no one taller or equal in front of them.
Person 1 has height 5 with no one taller or equal in front of them.
Person 2 has height 2 with two people taller or equal in front of them.
Person 3 has height 3 with two people taller or equal in front of them.
Person 4 has height 1 with four people taller or equal in front of them.
Person 5 has height 6 with no one taller or equal in front of them.

Constraints

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

Thinking Process

Tallest first: Process tallest people first
Tallest people: Can be placed anywhere without affecting others

Greedy works when local optimal choices lead to global optimum.
Often sort first to make the greedy choice obvious.
Prove or sanity-check: would swapping two choices ever help?

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Sort + greedy (this problem)	O(n log n)	O(1)	Interval scheduling, assignment
Local greedy choice	O(n)	O(1)	Jump game, gas station
Greedy + heap	O(n log n)	O(n)	Merge streams, room allocation
Exchange argument	O(n)	O(1)	Prove greedy choice is safe

Solution

Time Complexity: O(n²) where n is the number of people
Space Complexity: O(n) for the result list

Sort people by height (descending) and k-value (ascending), then insert each person at the k-th position using a list for efficient insertion.

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        /*
        1. Sort by height (descending), then by k-value (ascending)
        2. Insert each person at the k-th position
        3. Use list for efficient insertion at arbitrary positions
        */

        sort(people /* elements of people */, [](int[] a, int[] b) {
            if(a[0] == b[0]) return a[1] < b[1];  // Same height: sort by k-value
            return a[0] > b[0];                    // Different height: sort by height
        });

        list<int[]> rtn;
        for (int person : people) {
            var it = rtn.iterator();
            advance(it, person[1]);  // Move iterator to k-th position
            rtn.add(it, person);
        }

        return int[][](rtn /* elements of rtn */);
    }
}

Solution Explanation

Key Insight: Sort people by height (descending) and k-value (ascending), then insert each person at the k-th position.

Steps:

Sort people by height (descending) and k-value (ascending)
Use list for efficient insertion at arbitrary positions
For each person:
- Move iterator to k-th position
- Insert person at that position
Convert list to vector and return

Step-by-Step Example

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

Step 1: Sort by height (descending) and k-value (ascending)

Original: [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Sorted:   [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]

Step 2: Insert each person at k-th position

Person	Height	K	List State	Insertion Position
[7,0]	7	0	[]	Position 0 → [[7,0]]
[7,1]	7	1	[[7,0]]	Position 1 → [[7,0],[7,1]]
[6,1]	6	1	[[7,0],[7,1]]	Position 1 → [[7,0],[6,1],[7,1]]
[5,0]	5	0	[[7,0],[6,1],[7,1]]	Position 0 → [[5,0],[7,0],[6,1],[7,1]]
[5,2]	5	2	[[5,0],[7,0],[6,1],[7,1]]	Position 2 → [[5,0],[7,0],[5,2],[6,1],[7,1]]
[4,4]	4	4	[[5,0],[7,0],[5,2],[6,1],[7,1]]	Position 4 → [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

Final result: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

Algorithm Breakdown

Sorting Logic:

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        sort(people /* elements of people */, [](int[] a, int[] b) {
            if(a[0] == b[0]) return a[1] < b[1];
            return a[0] > b[0];
        });

        List<int[]> result = new ArrayList<>();
        for (int person : people) {
            result.add(result.iterator() + person[1], person);
        }

        return result;
    }
}

Process:

Primary sort: By height (descending)
Secondary sort: By k-value (ascending) for same height
Result: Tallest people first, then by k-value

Insertion Logic:

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        for (int person : people) {
            pq.offer({person[0], person[1]});
        }

        List<int[]> result = new ArrayList<>();
        while(!pq.isEmpty()) {
            int[] hpair = pq.peek(); int h = hpair[0]; int k = hpair[1];
            pq.poll();
            result.add(result.iterator() + k, new int[] {h, k});
        }

        return result;
    }
}

Process:

Start iterator at beginning of list
Advance iterator to k-th position
Insert person at that position
Repeat for all people

Complexity

| Operation | Time Complexity | Space Complexity | |———–|—————-|——————| | Sorting | O(n log n) | O(1) | | Insertion | O(n²) | O(n) | | Total | O(n²) | O(n) |

Where n is the number of people.

Detailed Example Walkthrough

Example: `people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]`

Step 1: Sort by height (descending) and k-value (ascending)

Original: [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
Sorted:   [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]

Step 2: Insert each person at k-th position

Person	Height	K	List State	Insertion Position
[6,0]	6	0	[]	Position 0 → [[6,0]]
[5,0]	5	0	[[6,0]]	Position 0 → [[5,0],[6,0]]
[4,0]	4	0	[[5,0],[6,0]]	Position 0 → [[4,0],[5,0],[6,0]]
[3,2]	3	2	[[4,0],[5,0],[6,0]]	Position 2 → [[4,0],[5,0],[3,2],[6,0]]
[2,2]	2	2	[[4,0],[5,0],[3,2],[6,0]]	Position 2 → [[4,0],[5,0],[2,2],[3,2],[6,0]]
[1,4]	1	4	[[4,0],[5,0],[2,2],[3,2],[6,0]]	Position 4 → [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

Final result: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

Common Mistakes

Single person: people = [[5,0]] → [[5,0]]
All same height: people = [[5,0],[5,1],[5,2]] → [[5,0],[5,1],[5,2]]
All k=0: people = [[7,0],[6,0],[5,0]] → [[5,0],[6,0],[7,0]]
Maximum k: people = [[1,2]] → [[1,2]]
Wrong sorting order: Not sorting by height descending first
Incorrect k-value handling: Not considering k-value for same height
Wrong insertion position: Inserting at wrong index
Data structure choice: Using vector instead of list for insertion

Why This Solution Works

Greedy Strategy:

Tallest first: Process tallest people first
K-value ordering: For same height, process by k-value
Insertion order: Insert at k-th position
Optimal result: Always produces correct reconstruction

List Efficiency:

O(1) insertion: Insert at arbitrary positions
Iterator advancement: Efficient position finding
Memory efficient: No extra space for insertion
Optimal performance: Better than vector insertion

Key Algorithm Properties:

Correctness: Always produces valid reconstruction
Optimality: Produces correct queue order
Efficiency: O(n²) time complexity
Simplicity: Easy to understand and implement

References

LC 406: Queue Reconstruction by Height on LeetCode
LeetCode Discuss — LC 406: Queue Reconstruction by Height
LeetCode Editorial (may require premium)

Key Takeaways

Greedy Strategy:

Tallest first: Process tallest people first
K-value ordering: For same height, process by k-value
Insertion order: Insert at k-th position
Optimal result: Always produces correct reconstruction

Why This Works:

Tallest people: Can be placed anywhere without affecting others
K-value constraint: Each person needs exactly k taller people in front
Insertion order: Maintains the constraint for all people
List efficiency: O(1) insertion at arbitrary positions

Robina Li

[Medium] 406. Queue Reconstruction by Height

Examples

Constraints

Thinking Process

Common Approaches

Solution

Solution Explanation

Step-by-Step Example

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

Algorithm Breakdown

Sorting Logic:

Insertion Logic:

Complexity

Detailed Example Walkthrough

Example: `people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]`

Common Mistakes

Why This Solution Works

Greedy Strategy:

List Efficiency:

Key Algorithm Properties:

References

Key Takeaways

Greedy Strategy:

Why This Works:

Related Posts

Recent Posts

Examples

Constraints

Thinking Process

Common Approaches

Solution

Solution Explanation

Step-by-Step Example

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

Algorithm Breakdown

Sorting Logic:

Insertion Logic:

Complexity

Detailed Example Walkthrough

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

Common Mistakes

Related Problems

Why This Solution Works

Greedy Strategy:

List Efficiency:

Key Algorithm Properties:

References

Key Takeaways

Greedy Strategy:

Why This Works:

Related Posts

Recent Posts

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

Example: `people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]`