LeetCode Problem 406

Difficulty: 🟡 Medium
Topics: Array, Binary Indexed Tree, Segment Tree, Sorting

Solution

LeetCode 406 - Queue Reconstruction by Height

Problem Understanding

This problem gives us a list of people where each person is represented as a pair [h, k].

The value h represents the person's height.

The value k represents how many people standing in front of this person must have a height greater than or equal to h.

Our task is to reconstruct the original queue arrangement so that every person's k condition is satisfied.

For example, if a person is [6,1], that means exactly one person in front of them must have height >= 6.

The input array is not necessarily ordered in any meaningful way. We must determine the correct arrangement ourselves.

The output must be a queue where every person satisfies their constraint simultaneously.

The constraints are important:

• There can be up to 2000 people.
• Heights can be as large as 10^6.
• The problem guarantees that a valid reconstruction always exists.

Since n is only 2000, an O(n^2) solution is acceptable because 2000^2 = 4,000,000, which is manageable. However, cubic solutions would likely be too slow.

Several edge cases are important:

• Multiple people may have the same height.
• Multiple people may have k = 0.
• The shortest people are the hardest to place greedily if we process in the wrong order.
• Equal-height people require careful ordering because they count toward each other's k values.
• A naive insertion strategy can easily invalidate previously placed people.

The guarantee that a valid queue exists simplifies the problem because we do not need to detect impossible states.

Approaches

Brute Force Approach

A brute-force solution would attempt to generate permutations of the people and check whether each arrangement satisfies all constraints.

For each permutation:

1. Traverse the queue.
2. Count how many previous people have height greater than or equal to the current person.
3. Verify whether the count equals k.

If all people satisfy their constraints, we return that permutation.

This approach is correct because it explicitly tests every possible ordering. Eventually, the valid arrangement will be found.

However, the complexity is disastrous. There are n! possible permutations, which becomes impossible even for relatively small values of n.

Even with pruning or backtracking optimizations, this approach is not practical for n = 2000.

Optimal Greedy Approach

The key insight is that taller people are unaffected by shorter people behind or around them.

Suppose we place the tallest people first.

When placing a tall person:

• Only people of equal or greater height matter for their k value.
• Shorter people do not affect the count.

This observation allows a greedy strategy.

We sort people by:

1. Height in descending order
2. k in ascending order for equal heights

Then we insert each person into the result at index k.

Why does this work?

Because when processing taller people first, the current queue already contains only people whose height is greater than or equal to the current person.

Therefore, inserting at index k guarantees exactly k qualifying people stand before them.

This elegant observation transforms the problem into a simple sorting and insertion process.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! × n)	O(n)	Tries every possible queue arrangement
Optimal Greedy	O(n²)	O(n)	Sort descending by height, then insert by k

Algorithm Walkthrough

Step 1: Sort the People

Sort the array using two rules:

1. Higher height first
2. Smaller k first when heights are equal

For example:

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

becomes:

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

This ordering is critical because taller people must be fixed before shorter people.

Step 2: Initialize an Empty Queue

Create an empty result list.

queue = []

We will gradually build the correct arrangement.

Step 3: Process Each Person in Sorted Order

Traverse the sorted array from left to right.

For each person [h, k]:

• Insert them into the queue at position k.

Why?

At this moment, all people already in the queue are at least as tall as the current person.

Therefore, placing the current person at index k ensures exactly k taller-or-equal people appear before them.

Step 4: Continue Until All People Are Inserted

Each insertion preserves correctness for previously placed taller people.

Eventually, the queue satisfies all constraints simultaneously.

Step 5: Return the Queue

Return the final reconstructed queue.

Why it works

The core invariant is:

Before inserting a person [h, k], the queue already contains only people with height greater than or equal to h.

Because of this invariant:

• The insertion index directly corresponds to the number of valid taller-or-equal people before the current person.
• Shorter people inserted later cannot affect the counts of taller people already placed.

Sorting by descending height guarantees this invariant always holds.

Python Solution

from typing import List

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # Sort by descending height, ascending k
        people.sort(key=lambda person: (-person[0], person[1]))

        queue = []

        # Insert each person at index k
        for person in people:
            queue.insert(person[1], person)

        return queue

The implementation begins by sorting the people according to the greedy ordering strategy.

The sorting key (-person[0], person[1]) ensures:

• Taller people come first
• Among equal heights, smaller k values come first

After sorting, we create an empty list called queue.

We then iterate through each person and insert them directly at index k.

Python's list.insert(index, value) automatically shifts later elements to the right, making it perfect for this problem.

Because taller people are inserted first, every insertion maintains the invariant required for correctness.

Finally, the completed queue is returned.

Go Solution

package main

import "sort"

func reconstructQueue(people [][]int) [][]int {
    // Sort by descending height, ascending k
    sort.Slice(people, func(i, j int) bool {
        if people[i][0] == people[j][0] {
            return people[i][1] < people[j][1]
        }
        return people[i][0] > people[j][0]
    })

    queue := make([][]int, 0)

    // Insert each person at index k
    for _, person := range people {
        index := person[1]

        queue = append(queue, nil)

        copy(queue[index+1:], queue[index:])

        queue[index] = person
    }

    return queue
}

The Go solution follows the exact same algorithmic strategy as the Python version.

Since Go slices do not provide a built-in insertion method like Python lists, we manually perform insertion:

1. Extend the slice using append
2. Shift elements to the right using copy
3. Place the new person at the target index

The sorting logic uses sort.Slice with a custom comparator.

There are no integer overflow concerns because all values fit comfortably within Go's standard integer range.

The implementation correctly handles empty slices and all edge cases covered by the Python version.

Worked Examples

Example 1

Input:

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

Step 1: Sort

Sorted order:

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

Step 2: Insert Sequentially

Current Person	Queue After Insertion
[7,0]	[[7,0]]
[7,1]	[[7,0],[7,1]]
[6,1]	[[7,0],[6,1],[7,1]]
[5,0]	[[5,0],[7,0],[6,1],[7,1]]
[5,2]	[[5,0],[7,0],[5,2],[6,1],[7,1]]
[4,4]	[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

Final answer:

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

Example 2

Input:

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

Step 1: Sort

Sorted order:

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

Step 2: Insert Sequentially

Current Person	Queue After Insertion
[6,0]	[[6,0]]
[5,0]	[[5,0],[6,0]]
[4,0]	[[4,0],[5,0],[6,0]]
[3,2]	[[4,0],[5,0],[3,2],[6,0]]
[2,2]	[[4,0],[5,0],[2,2],[3,2],[6,0]]
[1,4]	[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

Final answer:

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

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Sorting is O(n log n), but list insertion can cost O(n) for each person
Space	O(n)	The reconstructed queue stores all people

The dominant cost comes from insertion operations.

Although sorting requires only O(n log n) time, each insertion into the middle of a list may require shifting elements. Since we perform up to n insertions, the total insertion cost becomes O(n²).

This complexity is acceptable for n <= 2000.

Test Cases

from typing import List

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

        queue = []

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

        return queue

solution = Solution()

# Example 1 from problem statement
assert solution.reconstructQueue(
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
) == [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

# Example 2 from problem statement
assert solution.reconstructQueue(
    [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
) == [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

# Single person case
assert solution.reconstructQueue(
    [[1,0]]
) == [[1,0]]

# All same height
assert solution.reconstructQueue(
    [[5,0],[5,1],[5,2],[5,3]]
) == [[5,0],[5,1],[5,2],[5,3]]

# Increasing heights with k = 0
assert solution.reconstructQueue(
    [[1,0],[2,0],[3,0],[4,0]]
) == [[1,0],[2,0],[3,0],[4,0]]

# Duplicate heights with mixed k values
assert solution.reconstructQueue(
    [[6,0],[6,1],[6,2],[5,0]]
) == [[5,0],[6,0],[6,1],[6,2]]

# Larger mixed configuration
assert solution.reconstructQueue(
    [[9,0],[7,0],[1,9],[3,0],[2,7],[5,3],[6,0],[3,4],[6,2],[5,2]]
) == [[3,0],[6,0],[7,0],[5,2],[3,4],[5,3],[6,2],[2,7],[9,0],[1,9]]

Test Summary

Test	Why
Example 1	Validates standard mixed ordering
Example 2	Validates multiple zero insertions
Single person	Smallest possible input
All same height	Ensures equal-height ordering works correctly
Increasing heights with k = 0	Tests repeated front insertions
Duplicate heights with mixed k	Verifies stable handling of equal heights
Larger mixed configuration	Stress test for insertion correctness

Edge Cases

Multiple People with the Same Height

When several people share the same height, their relative ordering becomes extremely important.

For example:

[[5,0],[5,1],[5,2]]

If we do not sort equal heights by ascending k, inserting someone with a larger k first could invalidate later placements.

The implementation handles this correctly by sorting equal heights using ascending k.

Everyone Has k = 0

Consider:

[[1,0],[2,0],[3,0]]

Every person expects no taller-or-equal people in front.

This forces every newly inserted taller person toward the front of the queue.

The insertion logic naturally handles this because every insertion occurs at index 0.

Very Short People Appearing Late

Short people often require large k values because many taller people stand before them.

For example:

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

If shorter people were processed early, their counts would later change as taller people are inserted.

The algorithm avoids this issue entirely by processing taller people first, ensuring that later insertions of shorter people never affect taller people's constraints.