Watch 10 video solutions for Queue Reconstruction by Height, a medium level problem involving Array, Binary Indexed Tree, Segment Tree. This walkthrough by Techdose has 27,581 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith 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. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).
Example 1:
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]] Explanation: Person 0 has height 5 with no other people taller or the same height in front. Person 1 has height 7 with no other people taller or the same height in front. Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1. Person 3 has height 6 with one person taller or the same height in front, which is person 1. Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3. Person 5 has height 7 with one person taller or the same height in front, which is person 1. Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.
Example 2:
Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]] Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
Constraints:
1 <= people.length <= 20000 <= hi <= 1060 <= ki < people.lengthProblem Overview: You are given people represented as [h, k], where h is height and k is the number of people in front who have height greater than or equal to h. Reconstruct the original queue so every person’s k value is satisfied.
Approach 1: Greedy Sorting + List Insertion (O(n2) time, O(n) space)
The key observation: taller people do not get affected by shorter people placed later. Sort the array by height in descending order, and if heights are equal, sort by k ascending. Then iterate through the sorted list and insert each person at index k in the result list. Because all previously inserted people are taller or equal height, inserting at position k guarantees exactly k valid people ahead. Each insertion into a list costs O(n), giving overall O(n^2) time with O(n) extra space.
This approach relies heavily on sorting and array insertion mechanics. Once the ordering rule is understood, the implementation becomes short and reliable.
Approach 2: Binary Indexed Tree Placement (O(n log n) time, O(n) space)
An alternative uses a Binary Indexed Tree to track empty positions in the queue. First sort people by height ascending and by k ascending. Then treat the queue as empty slots. For each person, locate the position where exactly k taller-or-equal people will appear in front by querying the BIT for the (k+1)-th empty slot. Update the tree when a slot is filled. This reduces insertion cost from O(n) to O(log n).
The BIT stores prefix sums representing available positions. Each query finds the index whose cumulative count equals a target slot number. This keeps the total complexity at O(n log n) with O(n) space.
Approach 3: Segment Tree Slot Allocation (O(n log n) time, O(n) space)
A segment tree can replace the BIT for managing empty positions. Each node stores the number of available slots in its range. During reconstruction, perform a query to locate the index representing the required free slot and update the tree once that position is used. The complexity matches the BIT approach but with a slightly heavier constant factor.
Recommended for interviews: The greedy sorting plus insertion approach is what most interviewers expect. It demonstrates that you recognized the core ordering insight: place taller people first so shorter ones never invalidate earlier constraints. Mentioning the BIT or segment tree optimization shows deeper algorithm knowledge, but the greedy O(n2) method is usually sufficient and easier to implement under interview pressure.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Sorting + List Insertion | O(n^2) | O(n) | Standard interview solution. Simple logic and short implementation. |
| Binary Indexed Tree (Fenwick Tree) | O(n log n) | O(n) | Useful when optimizing insert operations by tracking empty slots. |
| Segment Tree Slot Allocation | O(n log n) | O(n) | Alternative to BIT when practicing advanced range query structures. |