Queue Reconstruction by Height
Problem Statement
You are given an array people, where each person is represented as [height, k]. The value k means there must be exactly k people in front of this person whose height is greater than or equal to height.
Return the queue reconstructed so every person satisfies their k value. The input is guaranteed to have at least one valid reconstruction.
Input
A two-dimensional integer array people, where people[i] = [height, k].
Output
A two-dimensional integer array representing a valid reconstructed queue.
Constraints
- •
1 <= people.length <= 2000 - •
0 <= height <= 10^6 - •
0 <= k < people.length - •
The queue can be reconstructed from the given people
Examples
Example 1
people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]Example 2
people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]Learning Objectives
- Discover why sorting taller people first makes each **k** value immediately usable.
- Explain the exchange argument behind inserting each person at index **k**.
- Recognise greedy problems where the right sort key turns a global constraint into a local action.
- Implement index-based insertion cleanly with a linked list style structure.
Intuition
The hard part is choosing which people can be placed without being disturbed later. If you place short people first, every taller person inserted later can change the short person count in front, so their k values are unstable.
Reverse the perspective: place taller people first. Once all already-placed people are at least as tall as the current person, inserting the current person at position k creates exactly k taller-or-equal people before them. Later insertions are shorter, so they never increase anyone's taller-or-equal count. The non-obvious greedy insight is the sort key: height descending, and for equal height, k ascending.
Common mistakes
- ×Sorting by **k** first and then trying to adjust heights afterward.
- ×Sorting height ascending, which lets later taller insertions invalidate earlier placements.
- ×Forgetting the equal-height tie-breaker by **k** ascending.
- ×Appending instead of inserting at index **k** after the descending-height sort.
Algorithm Explanation
Greedy strategy
Sort people by height descending. When two people have the same height, sort by k ascending. Then scan this order and insert each person into the current queue at index k.
Why it works
At the moment we insert a person, everyone already in the partial queue is at least as tall. Therefore the number of qualifying people before that person is exactly their insertion index. People inserted later are shorter, so they may stand before this person physically, but they do not count toward this person's k requirement.
Proof of correctness
Consider the first person in the sorted order where a valid optimal queue differs from the greedy placement. All earlier people are taller, or the same height with smaller k, and are placed consistently. The current person needs exactly k qualifying people before them, and among already-placed people all qualify. Moving this current person to index k among the placed taller-or-equal people satisfies their requirement. This move does not harm earlier people because the current person is no taller than them and, for equal height, has no smaller k than those already placed. It also cannot harm later people because they have not been placed yet and are no taller. Thus any optimal queue can be transformed to match the greedy choice step by step.
Algorithm
- Sort people by height descending.
- For equal heights, sort by k ascending.
- Create an initially empty list for the queue.
- For each sorted person, insert them into the list at index k.
- Convert the list back to a two-dimensional array and return it.
Solutions
Solution: Descending height sort with indexed insertion
Sort so every already-placed person is tall enough to matter for the current person's k value. Then the local action is direct: insert the current pair at index k.
Step-by-step
- Sort the array using height descending and k ascending as the tie-breaker.
- Maintain a list representing the reconstructed prefix.
- For each person in sorted order, insert the pair at position person[1].
- Return the list as an array once all people have been inserted.
O(n^2)
O(n)
Sorting costs O(n log n), but indexed insertion in a linked list still shifts or traverses positions, giving O(n^2) overall.
Java implementation
Dry Run
Sample input
people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]. Sort by height descending, then by k ascending.
| step | person inserted | insert index | queue before | queue after |
|---|---|---|---|---|
| 1 | [7,0] | 0 | [] | [[7,0]] |
| 2 | [7,1] | 1 | [[7,0]] | [[7,0],[7,1]] |
| 3 | [6,1] | 1 | [[7,0],[7,1]] | [[7,0],[6,1],[7,1]] |
| 4 | [5,0] | 0 | [[7,0],[6,1],[7,1]] | [[5,0],[7,0],[6,1],[7,1]] |
| 5 | [5,2] | 2 | [[5,0],[7,0],[6,1],[7,1]] | [[5,0],[7,0],[5,2],[6,1],[7,1]] |
| 6 | [4,4] | 4 | [[5,0],[7,0],[5,2],[6,1],[7,1]] | [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] |
The final queue is valid because each insertion counted only people already present, all of whom were tall enough to contribute. Later shorter insertions do not change those counts.
Interview Tips
Lead with the instability of placing short people first, then introduce the descending-height sort as the stabilising move. Interviewers care less about the data structure and more about whether you can justify why k becomes an insertion index after the sort. If asked about performance, mention that an order-statistics tree can improve indexed placement in languages or libraries that support it, but the standard interview solution is the clear O(n^2) insertion method.
Likely follow-ups
- How would you reconstruct the queue if **n** were very large and O(n^2) insertion was too slow?
- What changes if **k** counted strictly taller people instead of taller-or-equal people?
- Can you validate whether a proposed reconstructed queue satisfies all constraints?
- How would duplicate people with identical **height** and **k** be handled?
Similar Problems
Key Takeaways
- When later elements can invalidate earlier decisions, process the elements that cannot be affected first.
- For this problem, height descending makes **k** equal to an insertion index.
- The tie-breaker **k** ascending is necessary for equal-height people.
- A strong greedy proof often shows later work cannot break an earlier invariant.