Skip to main content

406 - Queue Reconstruction by Height

Difficulty: Medium | Pattern: Greedy + Sort | Company tags: Google, Amazon, Facebook

Problem Statement​

You are given an array people where people[i] = [hi, ki] represents the i-th person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

Reconstruct and return the queue that is represented by the input array people.

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]]

Approach: Sort + Insert — O(n²)​

Key insight: Sort by height descending, ties broken by k ascending. Insert each person at index k. Taller people are placed first, so inserting a shorter person at position k correctly places them behind exactly k taller people.

Algorithm Flow​

def reconstructQueue(people: list[list[int]]) -> list[list[int]]:
    # Sort by height descending, then by k ascending
    people.sort(key=lambda x: (-x[0], x[1]))
    
    result = []
    for person in people:
        result.insert(person[1], person)  # insert at index k
    
    return result

Dry Run​

people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

After sort: [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]

personresult after insert
[7,0][[7,0]]
[7,1][[7,0],[7,1]]
[6,1][[7,0],[6,1],[7,1]]
[5,0][[5,0],[7,0],[6,1],[7,1]]
[5,2][[5,0],[7,0],[5,2],[6,1],[7,1]]
[4,4][[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

Result: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] ✓

Why Sort Height Descending?​

When we insert a person of height h at index k, all previously inserted people are >= h. So there are exactly k people in front with height >= h. Shorter people inserted later don't affect the count since we insert by index.

Complexity​

  • Time: O(n²) — list insert is O(n) for each of n people
  • Space: O(n)

Key Terms​

TermDefinition
Greedy sortChoosing a processing order (tallest-first) so that each subsequent decision is locally correct and never needs revisiting.
Insertion indexThe position k at which a person is inserted, guaranteeing exactly k taller/equal people precede them.
Tie-breaking ruleSorting equal-height people by k ascending so their relative insertion order preserves correctness.
Stable placementOnce a taller person is inserted, later insertions of shorter people never change the relative order of taller people.

FAQ​

Q: Why sort by height descending and not ascending? A: Inserting taller people first guarantees that when a shorter person is inserted at index k, all people already placed are taller or equal, so the count of "people in front with height >= h" is exactly k.

Q: Why break ties by k ascending for equal heights? A: Among people of the same height, inserting the one with a smaller k first ensures it lands before the one with a larger k, satisfying both of their constraints without conflict.

Q: Can this be done faster than O(n²)? A: Yes — using a Binary Indexed Tree (Fenwick tree) or balanced BST to find the k-th empty slot, insertion can be done in O(n log n) total.

Q: What if two people have the same height and the same k? A: The input is guaranteed valid in this problem, so such a case would only occur if duplicate people exist, and any consistent tie-break order still produces a valid queue.

Q: What happens if k for the tallest person is not 0? A: The input is guaranteed valid/solvable, so the tallest person always has k = 0 (no one is taller, so no one can stand in front of them).

Quick Revision​

  • Problem: reconstruct a queue from [height, count_of_taller_or_equal_in_front] pairs.
  • Sort people by height descending, ties broken by k ascending.
  • Insert each person at index k into the growing result list.
  • Correctness: taller people are already placed, so inserting at k guarantees exactly k people in front are taller/equal.
  • Shorter people inserted later don't affect earlier counts since only index matters.
  • Time complexity O(n²) due to O(n) list insertion per person; space O(n).
  • Can be optimized to O(n log n) with a Fenwick tree for k-th empty slot lookup.
  • Classic example of "process in an order that makes each step trivially correct" greedy design.