406. Queue Reconstruction by Height

Problem¶

Given people as pairs \([h, k]\), reconstruct a queue where each person has exactly \(k\) people of height at least \(h\) before them.

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

Key trick¶

Process taller people first by sorting by decreasing height and increasing \(k\), then insert each person at index \(k\).

Trap¶

Sorting equal-height people by decreasing \(k\) breaks the insertion invariant.
Building from shorter people first is difficult because later insertions can change their counts.
List insertion makes the solution \(O(n^2)\), which is acceptable for the given limit.

Why is it interesting?¶

It turns a global queue constraint into a local insertion decision by ensuring that every person already placed is at least as tall as the current person.

Python solution¶

class Solution:
    def reconstructQueue(self, people: list[list[int]]) -> list[list[int]]:
        # Taller people are unaffected by later insertions of shorter people.
        # For equal heights, place smaller k values first.
        ordered = sorted(people, key=lambda person: (-person[0], person[1]))

        queue = []
        for person in ordered:
            # All existing people are at least as tall, so index k gives
            # exactly k qualifying people before this person.
            queue.insert(person[1], person)

        return queue

Sorting costs \(O(n \log n)\); list insertions cost \(O(n^2)\) overall.

Comment on my solution¶

The backtracking approach is exponential and cannot handle up to \(2000\) people.

It also has correctness issues:

The base case compares the growing queue with the shrinking input, so it may trigger halfway through.
A successful recursive result is ignored instead of being propagated.
The returned queue is later emptied during backtracking because it is the same mutable list.
Each feasibility check builds a temporary list, adding unnecessary work.
Debug printing makes an already expensive search substantially slower.

# WRONG
class Solution:
    def reconstructQueue(self, people: list[list[int]]) -> list[list[int]]:
        #    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
        # -> [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

        # - people[i] = [hi, ki]
        #   => j for people[i] must be >= ki
        #   => and for each t <= j, exactly ki, such [ht, kt] with ht >= hi
        # - sort descending people of first key
        #   -    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
        #     -> [[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]
        # - seems to be pair comparison of pairs
        # - the property is global
        # - could greedy work with a few swaps and comparison???
        # - frequency count somewhere???
        # - buckets + backtracking + pruning
        #   [[[5, 0], [7, 0]],
        #    [[6, 1], [7, 1]],
        #    [[5, 2]],
        #    [],
        #    [4, 4]]

        # let's try backtracking with pruning

        people.sort(key=lambda x: x[1])
        queue = []

        def can_append_to_queue(h,k):
            return len(list(filter(lambda x: x[0] >= h, queue))) == k

        def backtrack():
            if len(queue) == len(people):
                return queue

            for i, (h, k) in enumerate(people):
                if can_append_to_queue(h,k):
                    people.pop(i)
                    queue.append([h,k])
                    backtrack()
                    people.insert(i,[h,k])
                    queue.pop()
        backtrack()
        return queue