Problem Statement

Queue Reconstruction by Height

You are given a list of people waiting in a line. Each person is written as people[i] = [hi, ki]. The first number, hi, is that person's height. The second number, ki, is a count: it tells you how many people standing in front of this person are at least as tall as them (the same height or taller). The line got scrambled, and your job is to put it back in an order where every person's ki count is correct. The trick that makes this easy is greedy ordering: we sort everyone from tallest to shortest, then we drop each person into the line one at a time at the exact spot their ki number points to. Greedy means we make the obvious best move at each step and never look back. Here, the best move is to place the tallest people first. Once they are down, adding a shorter person never breaks a taller person's count, because a shorter person is not "at least as tall" and so does not get counted by anyone taller. That is why placing each person at index ki just works.

mediumGreedySortingGreedyTime: O(n^2) · Space: O(n)

Signals to notice

reconstruct queue by heighttaller people don't see shorter ones aheadinsert by height

Brute force first

Try all permutations and check validity. Factorial. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.

The key insight

Sort by height descending (ties by k ascending). Insert each person at index k in the result. Taller people are placed first, so inserting at index k naturally puts exactly k taller people ahead. for insertions. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

Trace it on `people=[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]`

sort by (-height, k) -> [7,0],[7,1],[6,1],[5,0],[5,2],[4,4]; result=[]
person=[7,0], insert at 0 -> result=[[7,0]]
person=[7,1], insert at 1 -> result=[[7,0],[7,1]]
person=[6,1], insert at 1 -> result=[[7,0],[6,1],[7,1]]
person=[5,0], insert at 0 -> result=[[5,0],[7,0],[6,1],[7,1]]
person=[5,2], insert at 2 -> result=[[5,0],[7,0],[5,2],[6,1],[7,1]]
person=[4,4], insert at 4 -> result=[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
return [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

What must stay true

When you insert a person of height h at index k, all previously inserted people are ≥ h (sorted descending). So exactly k of them are ahead — the k constraint is automatically satisfied. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

sort people by height DESC, then k ASC
result = []
for person [h, k] in people:
    result.insert(index=k, person)   # k taller already placed
return result

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Sorting by height ascending — that doesn't work because inserting shorter people first disrupts the positions of taller people added later. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.

Greedy Pattern