p81 — Queue Reconstruction by Height

Source: LeetCode 406 · Medium · Topics: Greedy, Sorting, Exchange Argument Companies (2024–2025): Google (high), Amazon (medium), Meta (medium), Stripe (medium) Loop position: The canonical 2D-sort-key greedy. Tests whether you can derive (not just recall) the “tallest-first, then insert at index” trick.

1. Quick Context

Input: list of (h, k) pairs — person of height h has k taller-or-equal people in front of them in some valid arrangement. Reconstruct the queue.

Insight: Sort by (-h, k) — tallest first, ties broken by ascending k. Iterate and insert(k, person) into the result list. Because already-placed people are all ≥ this person’s height, the count of “taller-or-equal in front” equals the insertion index k.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/queue-reconstruction-by-height/

STOP. 30-min timer. Try brute permutation first to internalize the constraint, then look for an invariant.

3. Prerequisite Concepts

  • Stable sort with composite key.
  • List insert(index, value) semantics (O(n)).
  • Exchange argument for proving greedy correctness.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Given (h, k) pairs, output the queue arrangement satisfying every person’s k constraint.

2. Clarify: Heights unique? Often yes; if duplicates, ties matter — same-height people count toward each other’s k.

3. Examples: [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] → [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]].

5. Brute: Permute all n! arrangements; check k for each.

6. Target: O(n²) (sort O(n log n) + n inserts at O(n) each).

7. Pattern: Sort by primary descending, secondary ascending; insert at index.

8. Develop: see solution.py.

9. Test: all same height; strictly decreasing; one person; duplicates.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 The exchange argument

Claim: place tallest first. Proof: shorter people don’t affect a taller person’s k-count, so inserting shorter people later cannot disturb already-placed taller people’s positions. Conversely, placing a shorter person first would require knowing where future taller people land — circular.

6.2 Why ascending k breaks ties

Among same-height people, the one with smaller k must come first (their k counts include the other same-height people). Sorting (-h, k) ensures [5,0] is placed before [5,2], and insert(0, [5,0]) then insert(2, [5,2]) produces [..., [5,0], _, [5,2], ...] correctly.

6.3 Why insert(k, person) is correct

When inserting person (h, k), every already-placed person has height ≥ h. So whatever index we insert at, that index = count of people in front who are taller-or-equal = k. Insert at k.

6.4 Complexity refinement

O(n²) with Python list. With a balanced BST or order-statistic tree (Fenwick of free slots), O(n log n). Rarely asked at the interview bar; mention as a follow-up.

6.5 Family: 2D-sort-key greedy

  • LC 406 Queue Reconstruction (this).
  • LC 354 Russian Doll Envelopes (sort by w asc, h desc → LIS on h).
  • LC 452 Min Arrows Burst Balloons (sort by end asc).
  • LC 1235 Job Scheduling (sort by end, DP + binary search).

The pattern: choose primary key for the “anchor” invariant, secondary key to disambiguate ties.

6.6 When greedy intuition is wrong

If heights could be unbounded and k could exceed n, the problem is ill-posed. The greedy assumes a valid queue exists; doesn’t verify.

7. Anti-Pattern Analysis

  1. Sort by height ascending — already-placed shorter people don’t satisfy the “taller-or-equal” predicate, so index ≠ k.
  2. Sort ties by descending k — places [5,2] before [5,0], breaking the same-height ordering invariant.
  3. Append instead of insert — produces wrong positions.
  4. Forget that k counts same-height people too — easy to convince yourself k is “strictly taller”.
  5. Try DP — exponential states; greedy is asymptotically better and conceptually cleaner.
  6. Brute permutation in production code — n! grows; only acceptable as oracle.

8. Skills & Takeaways

  • 2D sort key design.
  • Exchange argument for greedy correctness.
  • Why insertion-by-rank works when prefix is “all ≥”.

9. When to Move On

  • Solve cold in 20 min, articulate the exchange argument unprompted.
  • Justify each sort key direction.
  • Cite Russian Doll Envelopes as a sibling.

10. Company Context

  • Google: L4/L5; greedy correctness signal.
  • Amazon: L5; sort-then-insert template.
  • Meta: E4/E5; common 2D-sort warmup.
  • Stripe: mid; loves greedy proof questions.

Strong: “Sort tallest-first ties broken by ascending k, insert at index k; cold; exchange argument articulated; cited 2D-sort family.”

11. Interviewer’s Lens

SignalJuniorMidSeniorStaff+
Sort keyGuessesAfter hintCold+ derives from exchange
Tie-breakMissesBackwardsCorrect+ proves both directions wrong
Insert vs appendAppendAfter testInsert+ cites O(n log n) refinement
FamilyNoneNoneRussian Dolls+ Job Scheduling sibling

12. Level Delta

  • Mid (L4): Greedy after hint; struggles with tie-break direction.
  • Senior (L5): Sort + insert cold; correct tie-break; explains exchange argument.
  • Staff (L6): + Fenwick-of-free-slots O(n log n) refinement + 2D-sort-key family.
  • Principal (L7+): + connects to topological-sort variants + when exchange arguments fail (matroid intersection NP-hard in general).

13. Follow-up Q&A

Q1: Heights with duplicates — does tie-breaking matter? A1: Yes. Ascending k among same heights is required.

Q2: What if k can equal the number of people not less than h (instead of taller-or-equal)? A2: Strict version. Sort ties differently; insert offset by count of same-height already inserted. Solvable; cleaner with explicit predicate.

Q3: Streaming version — people arrive one by one? A3: Order-statistics tree of empty slots; O(n log n).

Q4: How to verify an arrangement is valid? A4: For each person, count j < i with height[j] >= height[i]; compare to k. O(n²).

Q5: What if no valid arrangement exists? A5: Our greedy still outputs something; verify with Q4 to detect.

14. Solution Walkthrough

See solution.py:

  • reconstruct_queue — sort + insert; O(n²).
  • reconstruct_queue_fenwick — Fenwick of free slots; O(n log² n).
  • reconstruct_queue_brute — try all permutations; oracle.

15. Beyond the Problem

Principal code review: “Queue Reconstruction is the smallest exchange-argument problem with a 2D sort key. The lesson scales: in distributed systems, you constantly face ‘order-by-key-A-then-key-B’ problems — Spanner timestamps (commit-time then transaction-id), Kafka partition-then-offset, paxos round-then-proposer. The exchange argument generalizes: when you can prove that swapping two adjacent items in violation of the order strictly worsens the objective, the sorted order is optimal. The deeper move at Staff+: recognize that greedy works iff the underlying problem is a matroid (Edmonds’ theorem). Queue Reconstruction is a degenerate matroid (the free-slot poset); Russian Dolls is the partial-order matroid; job scheduling is a transversal matroid. When the problem isn’t a matroid, greedy still might work, but you owe a proof — usually via exchange or via reduction to a known matroid.”