Queue Reconstruction by Height
Understanding the Problem
We have a shuffled list of people, and each person tells us two things: their height, and how many people who are at least as tall stand in front of them in the original queue. We need to figure out the original ordering.
The constraint that drives every solution is that k only counts people who are taller or equal, not shorter. A short person standing in front of a tall person does not change the tall person's k value. This asymmetry is what makes a greedy ordering possible.
Stated differently, a person of height 7 counts only other people of height 7 or more in front of them. People of height 4, 5, or 6 are irrelevant to that count. So if we fix the positions of all the tall people first, we can place shorter people afterward without changing any tall person's count.
Key Constraints
1 <= people.length <= 2000: With n up to 2000, an O(n^2) approach runs in about 4 million operations and passes comfortably. An O(n log n) approach exists and is the focus of the final section.0 <= k_i < people.length: Everykis in range, and the problem guarantees a valid reconstruction exists, so we never have to detect an impossible input.0 <= h_i <= 10^6: Heights can be large. We only compare and sort them, so the magnitude never matters and there is no overflow risk.
Approach 1: Brute Force (Try All Permutations)
Intuition
Try every possible ordering of the people and check which one satisfies all the constraints. For each permutation, verify that every person has exactly k people taller or equal in front of them.
This is simple but impractical. With n people there are n! permutations, and for n = 10 that is already 3.6 million orderings, each needing O(n^2) to verify. For n = 2000 it is far beyond any time limit. We include it only to fix the validity check we are aiming for, then improve from there.
Algorithm
- Generate all permutations of the
peoplearray. - For each permutation, check if it forms a valid queue:
- For each person at position
j, count how many people at positions0toj-1have height >= this person's height. - If the count equals
kfor every person, this permutation is the answer. - Return the valid permutation.
Visualization and Code
Loading animation...
- Time Complexity: O(n! * n^2). There are n! permutations, and validating each takes O(n^2) since we check each person's count against all people in front.
- Space Complexity: O(n). We store the current permutation order and the result array.
The brute force ignores the structure in each person's k value. If we process people in the right order, k tells us directly where to place each one, with no search at all.
Approach 2: Greedy (Sort by Height Descending + Insert by k)
Intuition
A tall person's count depends only on taller-or-equal people. A person of height 7 with k = 1 needs exactly 1 person of height 7 or more in front of them, and shorter people in front do not change that count.
So we place the tallest people first. While the queue contains only tall people, each one's k value is exactly the index where it belongs, because everyone already placed is taller or equal.
When we later insert a shorter person at index k, every person already in the list is taller or equal, so the insertion puts exactly k taller-or-equal people in front of them. The insertion also does not change the count of anyone already placed, because those people are all taller or equal and do not count the newcomer.
The sort is by height descending, breaking ties by k ascending. The tie-break matters: among people of equal height, the one with the smaller k belongs further left. Placing it first, at the smaller index, leaves the equal-height person with the larger k to land to its right when inserted later, which is the order their k values require.
The invariant is that once a person is placed, the number of taller-or-equal people in front of them never changes again. When we insert [h, k], every person already in the list has height >= h, so positions 0 to k-1 hold exactly k taller-or-equal people, which is what k requires.
Any person inserted afterward is shorter or equal. If it lands to the left of an already-placed person, it is shorter, so it does not add to that person's count. If it is equal in height, the tie-break ordering placed the smaller-k person first, so the equal-height newcomer lands to the right and still does not increase the earlier person's count. Every placement therefore stays correct through the end.
Algorithm
- Sort
peopleby height in descending order. For people with the same height, sort bykin ascending order. - Create an empty result list.
- Iterate through the sorted array. For each person
[h, k], insert them at indexkin the result list. - Return the result list.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2). Sorting takes O(n log n). Each insertion into the list at an arbitrary index takes O(n) in the worst case (shifting elements), and we do n insertions, so the total is O(n^2).
- Space Complexity: O(n). We use a result list of size n. The sort may use O(log n) stack space internally.
The cost here is the insertion. Each insert at an arbitrary index shifts every element after it, which is O(n) per person and O(n^2) overall. The next approach removes the shifting by sorting the other direction and computing each final position with a data structure that answers "where is the k-th open slot" in logarithmic time.
Approach 3: Optimal (Sort by Height Ascending + Segment Tree for Empty Slots)
Intuition
Process the shortest people first. When we place the shortest person, everyone not yet placed is taller or equal, so that person's k value tells us they need k taller-or-equal people in front. Every remaining empty slot will eventually hold a taller-or-equal person, so the person belongs in the (k+1)th empty slot from the left: skip k empty slots, then take the next one.
The sort is by height ascending, breaking ties by k descending. Among people of equal height, the one with the larger k is placed first, into a later empty slot. When the equal-height person with the smaller k is placed afterward, it lands in an earlier empty slot, which is the correct relative order for two people of the same height.
A direct scan for the (k+1)th empty slot costs O(n) per person, giving O(n^2). The improvement is to answer "which index is the (k+1)th empty slot" in O(log n) with a segment tree over slot positions. Each leaf holds 1 if its slot is empty and 0 once filled, and each internal node stores the sum of its children, the number of empty slots in its range. To find the (k+1)th empty slot, descend from the root: if the left child has more than k empty slots the target is on the left, otherwise subtract the left child's count from k and go right. When we reach a leaf, that is the slot; set it to 0 and propagate the change upward.
Processing shortest first means every unplaced person is taller or equal to the current one, so every empty slot is a future home for a taller-or-equal person. Putting the current person in the (k+1)th empty slot leaves exactly k empty slots to its left, each destined for a taller-or-equal person, which satisfies its k. Slots already filled to the left hold people that are shorter or equal (placed earlier) and never get counted incorrectly, because a person inserted earlier was shorter, and shorter people do not contribute to this person's count.
The segment tree returns the same slot a linear scan would. Descending right after subtracting the left subtree's empty count is equivalent to skipping those empty slots, so the tree finds the (k+1)th empty position exactly, in O(log n) per query.
Algorithm
- Sort
peopleby height ascending. For the same height, sort bykdescending. - Build a segment tree over n leaves, each initialized to 1 (every slot starts empty). Internal nodes store the count of empty slots in their range.
- For each person
[h, k]in sorted order: - Query the tree for the index of the
(k+1)th empty slot (skipkempty slots from the left). - Place the person there and set that leaf to 0, updating ancestors.
- Return the result array.
Visualization and Code
Loading animation...
- Time Complexity: O(n log n). Sorting is O(n log n). Building the segment tree is O(n), and each of the n placements does one query plus update in O(log n), for O(n log n) total. The recursion descends one root-to-leaf path per placement, so the depth is O(log n).
- Space Complexity: O(n). The segment tree uses 4n entries and the result array holds n people. The recursion stack is O(log n) deep, which is dominated by O(n).