Queue Reconstruction by Height: Greedy Insertion

You are given an array of people where people[i] = [h_i, k_i]. Each person has a height h_i and a value k_i representing how many people in front of them have a height greater than or equal to h_i. Your job is to reconstruct the queue so that every person's k value is satisfied. This is LeetCode 406: Queue Reconstruction by Height, a medium problem that rewards a clean greedy insight.

The approach: sort tall first, insert at k

The key insight is this: if you process people from tallest to shortest, each person you insert only cares about people already in the queue. Since everyone already placed is at least as tall, the k value tells you exactly which index to insert at.

Think about it from the tallest person's perspective. When you place them first, the queue is empty or contains only people of equal height. Their k value directly corresponds to their position. When you then place a shorter person, they "see" everyone already in the queue as taller or equal. So their k value is exactly the index where they belong. Inserting a shorter person never disrupts the k values of taller people already placed, because shorter people are invisible to the taller ones' k counts.

The algorithm has two steps:

1. Sort the people by height descending. For people with the same height, sort by k ascending. This ensures that when two people share a height, the one needing fewer tall people in front gets placed first.
2. Insert each person into the result at index k. Because everyone already in the result is at least as tall, the index k is exactly the right position.

def reconstructQueue(people):
    people.sort(key=lambda x: (-x[0], x[1]))
    queue = []
    for p in people:
        queue.insert(p[1], p)
    return queue

Complexity

Sorting takes O(n log n). The bottleneck is the insertion loop: each list.insert at an arbitrary index takes O(n) in the worst case because elements after the insertion point must shift right. Over n insertions, this totals O(n^2). The space is O(n) for the output queue.

Can you do better than O(n^2)? In theory, you could use a binary indexed tree or a segment tree to find insertion positions in O(log n) each, bringing the total to O(n log n). But for interview purposes, the O(n^2) greedy insertion is the expected solution. It is clean, easy to explain, and runs well within typical constraints (n up to a few thousand).

The building blocks

Greedy ordering by priority. Sorting by one dimension to simplify decisions about another is a recurring greedy pattern. Here you sort by height so that the k constraint reduces to a simple index. You see the same idea in problems like Candy (sort by rating to determine distribution order) and in interval scheduling (sort by end time to maximize non-overlapping intervals). The pattern is: identify which dimension, when fixed, makes the other dimension trivial to resolve.

Insertion-order invariant. The trick of processing elements in an order that guarantees previously placed elements remain valid after each new insertion. When you insert short people among tall people, the tall people's k values stay correct because short people do not count toward their k. This "invisible to earlier elements" property is what makes the greedy approach work without backtracking.

Stable multi-key sorting. Sorting by a primary key descending and a secondary key ascending (or vice versa) to control processing order. The secondary key (k ascending for ties in height) ensures that among people of the same height, the person needing fewer tall people in front is placed first, which keeps subsequent insertions at the correct indices.

Edge cases

• All same height [[5,0],[5,1],[5,2]]: everyone has the same height, so k values simply dictate their positions. Sorting by k ascending and inserting at index k produces the identity ordering.
• Already sorted input [[4,0],[5,0],[6,0],[7,0]]: every person has k=0. After sorting by height descending, each person gets inserted at index 0, reversing the order to [[7,0],[6,0],[5,0],[4,0]], which is correct since nobody taller stands in front.
• Single person [[3,0]]: one person, k must be 0. The result is just [[3,0]].
• Two people with swapped positions [[6,1],[7,0]]: sort gives [[7,0],[6,1]]. Insert [7,0] at 0, then [6,1] at 1. Result [[7,0],[6,1]], which is valid.

From understanding to recall

The greedy insertion for queue reconstruction is one of those solutions that feels obvious once you see it, but is surprisingly hard to reproduce from scratch. The details that trip people up: remembering to sort by height descending and k ascending, and understanding why shorter people do not affect taller people already placed.

Spaced repetition locks in the sort key and the insertion logic separately. You practice writing key=lambda x: (-x[0], x[1]) from memory until the negative sign and the tuple ordering are automatic. Then you practice the insert loop until the two-line core of the algorithm flows without hesitation. After a few repetitions at increasing intervals, you stop thinking about which direction to sort or why the insertion index is k. It just comes out.

This problem also reinforces the broader greedy pattern of choosing a processing order that simplifies decisions. Once you have drilled that pattern across several problems (Candy, Gas Station, Jump Game II), you start recognizing it instantly. The question shifts from "how do I solve this?" to "which dimension do I sort first?" and the answer follows naturally.

Related posts

• Candy - Another greedy problem requiring multiple passes with ordering constraints
• Gas Station - Greedy problem with a cyclic structure
• Jump Game II - Greedy forward-looking algorithm