← DSA Atlas
Dedicated problem page · #406

Queue Reconstruction by Height

MediumGreedy AlgorithmsGreedy sort then insert by positionGreedy ordering with insertion
Solve on LeetCode ↗
406
MediumGreedy AlgorithmsGreedy ordering with insertionGreedy sort then insert by position

Queue Reconstruction by Height

You are given an array people where people[i] = [h_i, k_i] means the i-th person has height h_i and exactly k_i people in front of them who are at least as tall. Reconstruct and return the queue (as a list of [h, k] pairs) that satisfies every person's k count.

Open official problem prompt ↗
In plain English

Rebuild the original line so that each person has exactly the stated number of equal-or-taller people standing ahead of them.

Picture it like this

Like seating guests tallest-first: since anyone already seated can be seen over the newcomers, a new person's 'count ahead' is just the seat number you slide them into.

Example
Input
people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output
[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
Why
Every person ends up with exactly k taller-or-equal people ahead of them, e.g. [4,4] has four people of height >= 4 in front.
Constraints
1 <= people.length <= 20000 <= h_i <= 10^60 <= k_i < people.length
Pattern lesson

See the pattern, then code

Greedy sort then insert by position
Recognition clue

Each element's constraint counts only OTHERS at least as tall, which becomes trivially satisfiable if you place people tallest-first: shorter people inserted later never affect earlier counts.

↗
Greedy Algorithms

A locally best action can be justified by an exchange argument or invariant.. Process people from tallest to shortest; when inserting a person, everyone already placed is at least as tall, so their k value is exactly the index at which they belong.

New words, made simpleKnow these before the algorithm
k value
The number of people at least as tall who must stand in front of this person.
insert at index k
Placing a person so exactly k already-placed (taller-or-equal) people precede them.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Brute-force permutations

Astronomically slow.

Try orderings until every k constraint holds.

Time O(n! * n)Space O(n)
Sort shortest-first

Works but requires tracking empty slots; more error-prone.

Place shorter people first and reserve gaps for taller ones.

Time O(n^2)Space O(n)
Best choiceTallest-first insertion

Clean and correct because later (shorter) insertions never disturb earlier counts.

Sort by height descending (k ascending on ties) and insert each at index k.

Time O(n^2)Space O(n)
The rule we keep true

Invariant

At every step, the partial queue contains only people at least as tall as the one being inserted, so inserting at index k gives that person exactly k taller-or-equal people in front.

Why this is correct

Reasoning

Inserting a shorter person later never changes the count of taller-or-equal people in front of anyone already placed (the newcomer does not count toward them). Sorting equal heights by ascending k ensures that among same-height people the one needing fewer in front is placed first, keeping their relative order correct.

The algorithm in three movesSay these aloud before coding
1Sort people by height descending, and by k ascending within equal heights

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

2Start with an empty result list

insert [7,0]@0, [7,1]@1 -> [[7,0],[7,1]]

3Insert each person at list index k

insert [6,1]@1 -> [[7,0],[6,1],[7,1]]

4Return the reconstructed list

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
[7,0]0
[7,1]1
[6,1]2
[5,0]3
[5,2]4
[4,4]5
1 · Readraw people
2 · AskOrder?
3 · Update state[[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]
4 · ResultTallest-first, k ascending on ties.
Key takeaway

People sorted tallest-first; each is inserted at the index equal to its k value.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 2Sort key

    -p[0] orders tallest first; p[1] breaks height ties by ascending k so smaller counts insert earlier.

  2. 2
    Lines 3-5Greedy insertion

    Each person is dropped at index k, valid because all already-placed people are at least as tall.

  3. 3
    Lines 6Return queue

    After all insertions the list satisfies every k constraint.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A single person returns that person unchanged
  • All people the same height reduce to placing them at their k positions in order
  • All k = 0 yields the people sorted tallest-first
!

Common beginner mistakes

  • Sorting equal heights by descending k, which places same-height people in the wrong relative order
  • Sorting shortest-first without slot bookkeeping, which breaks the count
  • Appending instead of inserting at index k
Check your understanding

Why can inserting a shorter person never invalidate an already-placed person's k?

More in Greedy Algorithms

#45Jump Game IIGreedy BFS by reachable layers#53Maximum SubarrayRunning best-ending-here (Kadane)#55Jump GameGreedy farthest-reach#134Gas StationGreedy single pass with tank reset#135CandyTwo-pass greedy (left-to-right then right-to-left)#678Valid Parenthesis StringGreedy Algorithms