Domain 2MediumCORE

Queue Reconstruction by Height

We are given a list of people where each person has two attributes: height h and an integer k. The value k represents the number of people standing in front (to the left) who have a height greater than or equal to h. We need to reconstruct the original queue order.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Greedy

406. Queue Reconstruction by Height

Model: qwen3.5:9b
Topics: Greedy
FAANG asked: 1
Acceptance rate: 68.6%


Problem Breakdown

We are given a list of people where each person has two attributes: height h and an integer k. The value k represents the number of people standing in front (to the left) who have a height greater than or equal to h. We need to reconstruct the original queue order.

Inputs:

  • A list of lists, where each inner list is [height, k].
  • Constraints: Length up to 2000, heights are non-negative integers. It’s guaranteed a valid solution exists.

Outputs:

  • The reconstructed queue array representing the correct order from front (index 0) to back.

Implicit Considerations:

  • Order of processing matters. If we process people randomly or by height ascending, determining where someone goes becomes ambiguous because shorter people don’t affect taller people’s counts (k). We must ensure that when we place a person, the k count reflects exactly how many valid predecessors are already in our list.
  • Duplicates: Multiple people can have the same height and different k. The relative order of these duplicates is critical (the one with smaller k comes first among equals).

Intuition

Let’s start by thinking about a brute-force approach: Try to insert each person into an initially empty list at index k, then check if their condition holds. However, checking the condition requires scanning all previous elements every time we place someone, and inserting shifts existing elements. Doing this naively for everyone would be O(N2)O(N^2) just by insertion alone, but without a smart ordering strategy, it might not even yield the correct configuration because placing a short person early affects where tall people can go later? Actually, if I place a short person first, they don’t count towards anyone else’s k (since others are taller). But wait, their presence does occupy an index.

The key insight is to look at who contributes most significantly to the “taller or equal” constraint: Tall people. If we place a tall person first, they don’t care about shorter people yet because those shorter people won’t count towards k (since hshort<hcurrenth_{short} < h_{current}). However, if we process from tallest height down to shortest:

  1. When we insert a person of height HH, all currently placed people have height ≥H\ge H.
  2. Therefore, any index position in our current list corresponds exactly to the number of taller-or-equal people standing before them.
  3. If k says “I need X people taller/equal in front”, and we are inserting into a queue where everyone else is already valid (taller or equal), then simply placing this person at index X satisfies their requirement perfectly, because there will be exactly X elements before them.

So the strategy: Sort by height descending. If heights match, sort by k ascending. Then iterate and insert each [h, k] into our result list at index k.

Approach

  1. Sorting: We first create a sorted version of the input array. The primary key is height in descending order (tallest first). The secondary key is k in ascending order (for same heights, those with fewer taller people ahead come earlier). This ensures that when we encounter two people of equal height, the one who needs fewer predecessors gets placed first among them.
  2. Insertion: We initialize an empty list for our result queue. We iterate through each person from the sorted array. For a person [h, k], we use list.insert(k, [h, k]). Since all people currently in the list are taller or equal to current height (due to sorting), placing them at index k ensures exactly k valid predecessors exist before them.
  3. Result: After iterating through everyone, return the constructed queue.

Complexity Analysis

  • Time Complexity: O(N2)O(N^2). Sorting takes O(Nlog⁡N)O(N \log N). The loop runs NN times. Inside the loop, list.insert is an insertion into a dynamic array (like Python’s list), which requires shifting elements and takes O(M)O(M) where MM is current length of queue (11 to N−1N-1). Summing this up gives ∑i=0N−1i≈O(N2)\sum_{i=0}^{N-1} i \approx O(N^2). Given the constraint people.length <= 2000, N2=4,000,000N^2 = 4,000,000, which is well within standard time limits for Python (typically allowing ~10710^7 operations per second).
  • Space Complexity: O(N)O(N) to store the output queue. The sorting operation uses auxiliary space depending on implementation (O(log⁡N)O(\log N) or O(N)O(N)), but this is dominated by the result array size.

Solution

from typing import List

def reconstructQueue(people: List[List[int]]) -> List[List[int]]:
    # Sort people by height descending, then k ascending for same heights
    # This ensures taller people are placed first, and among equals, 
    # those needing fewer predecessors come earlier.
    people.sort(key=lambda x: (-x[0], x[1]))
    
    queue = []
    
    # Iterate through sorted list and insert at index k
    for h, k in people:
        queue.insert(k, [h, k])
        
    return queue

# Example usage (commented out to keep solution clean)
# print(reconstructQueue([[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]])) 

Edge Cases Handled

  • Empty Input: Constraints guarantee people.length >= 1, so no empty list handling needed.
  • Duplicate Heights: The secondary sort key (k ascending) correctly handles duplicates by ensuring the person with a smaller k is placed before another of equal height, satisfying their respective counts relative to each other and taller people.
  • Large Height Values: Since we only compare heights for sorting order (not arithmetic operations on them), large integers (10610^6) are handled natively without overflow issues in Python.
  • Guaranteed Validity: The problem guarantees a solution exists, so no validation logic is required to check if k exceeds current queue length or similar inconsistencies.