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.
In this approach, we first sort the array of people. The sorting criteria should be descending order of height and ascending order of the number of people in front for the same height. After sorting, we iterate through the list and insert each person into a new list at the index corresponding to the number of people in front of them. This ensures that each person is placed correctly with regard to the number of taller or equally tall people in front.
This C solution sorts the list with a custom comparator and then builds the resulting queue by inserting each person at their k-th index. The qsort is used for sorting the list based on the height in descending order and the k-value in ascending order. We use an auxiliary array to store the reconstructed queue, shifting elements as needed during insertion to maintain order.
Time Complexity: O(n^2) due to the potential element shifting during insertion.
Space Complexity: O(1) additional space required.
| Approach | Complexity |
|---|---|
| Greedy Insertion Approach | Time Complexity: |
| Default Approach | — |
| 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. |
Queue Reconstruction by Height | Leetcode #406 • Techdose • 29,402 views views
Watch 9 more video solutions →Practice Queue Reconstruction by Height with our built-in code editor and test cases.
Practice on FleetCode