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
queuearray 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, thekcount 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 smallerkcomes 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 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 ). However, if we process from tallest height down to shortest:
- When we insert a person of height , all currently placed people have height .
- Therefore, any index position in our current list corresponds exactly to the number of taller-or-equal people standing before them.
- If
ksays “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 indexXsatisfies their requirement perfectly, because there will be exactlyXelements 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
- 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
kin 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. - 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 uselist.insert(k, [h, k]). Since all people currently in the list are taller or equal to current height (due to sorting), placing them at indexkensures exactlykvalid predecessors exist before them. - Result: After iterating through everyone, return the constructed queue.
Complexity Analysis
- Time Complexity: . Sorting takes . The loop runs times. Inside the loop,
list.insertis an insertion into a dynamic array (like Python’s list), which requires shifting elements and takes where is current length of queue ( to ). Summing this up gives . Given the constraintpeople.length <= 2000, , which is well within standard time limits for Python (typically allowing ~ operations per second). - Space Complexity: to store the output queue. The sorting operation uses auxiliary space depending on implementation ( or ), 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 (
kascending) correctly handles duplicates by ensuring the person with a smallerkis 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 () 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
kexceeds current queue length or similar inconsistencies.