LeetCode 406: Queue Reconstruction by Height

Problem Restatement

We are given a list of people.

Each person is represented as:

[h, k]

where:

We must reconstruct the original queue.

Return the queue in any valid order.

Input and Output

Example function shape:

def reconstructQueue(people: list[list[int]]) -> list[list[int]]:
    ...

Examples

Consider:

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

The answer is:

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

Let us verify a few positions.

For:

[5,0]

there are zero people in front with height at least 5.

Correct.

For:

[6,1]

there is exactly one person in front with height at least 6:

[7,0]

Correct.

For:

[4,4]

there are exactly four people in front with height at least 4.

Correct.

First Thought: Place Shorter People First

A natural idea is to place people from shortest to tallest.

But this causes problems.

When a taller person is inserted later, it changes the counts seen by shorter people already placed.

Example:

[5,0]

may initially satisfy its condition, but inserting taller people before it later changes how many taller-or-equal people stand in front.

So building from short to tall is unstable.

Key Insight

Taller people are unaffected by shorter people behind or in front of them.

If we place taller people first, then inserting shorter people later cannot change the number of taller-or-equal people before them.

This suggests:

1. Sort people by height descending.
2. For equal heights, sort by k ascending.
3. Insert each person at index k.

Why does insertion at index k work?

Because all previously inserted people are at least as tall as the current person.

So inserting at position k guarantees exactly k taller-or-equal people appear before the current person.

Algorithm

Sort people using:

height descending
k ascending

Then:

1. Start with an empty queue.
2. For each person in sorted order:
   • Insert the person at index k.
3. Return the queue.

Correctness

After sorting, people are processed from tallest to shortest.

Suppose we are inserting a person:

[h, k]

At this moment, every person already in the queue has height:

>= h

because taller people were processed first.

When we insert the current person at index k, exactly k people stand before them in the queue.

Since all those people have height at least h, the condition for [h, k] is satisfied immediately.

Later insertions involve only shorter people. Shorter people do not affect the count of people with height at least h.

Therefore, once a person is correctly placed, their condition remains correct forever.

Since every person is inserted in a valid position and no later operation breaks previous conditions, the final queue is correct.

Complexity

Sorting costs:

O(n log n)

but repeated insertions dominate the total complexity.

Implementation

class Solution:
    def reconstructQueue(self, people: list[list[int]]) -> list[list[int]]:
        people.sort(key=lambda p: (-p[0], p[1]))

        queue = []

        for person in people:
            queue.insert(person[1], person)

        return queue

Code Explanation

We first sort the people:

people.sort(key=lambda p: (-p[0], p[1]))

The key means:

Example sorted order:

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

Then we build the queue:

queue = []

For each person:

queue.insert(person[1], person)

If:

person = [6,1]

then inserting at index 1 guarantees exactly one taller-or-equal person appears before them.

Python list insertion automatically shifts later elements to the right.

Finally:

return queue

returns the reconstructed queue.

Testing

def test_reconstruct_queue():
    s = Solution()

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

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

    assert s.reconstructQueue(people1) == expected1

    people2 = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]

    result2 = s.reconstructQueue(people2)

    for i, (h, k) in enumerate(result2):
        count = sum(1 for x in result2[:i] if x[0] >= h)
        assert count == k

    people3 = [[1,0]]

    assert s.reconstructQueue(people3) == [[1,0]]

    people4 = [[5,0],[5,1],[5,2],[5,3]]

    result4 = s.reconstructQueue(people4)

    for i, (h, k) in enumerate(result4):
        count = sum(1 for x in result4[:i] if x[0] >= h)
        assert count == k

    print("all tests passed")

Test Notes