Queue Reconstruction by Height
Medium · Arrays & Hashing · Array · Greedy · Sorting
Problem
You are given an array people describing a queue whose order has been lost. Each entry people[i] = [h_i, k_i] says that person i has height h_i and that exactly k_i people standing in front of them have a height greater than or equal to h_i.
Rebuild the queue and return it in the same [h, k] format, where index 0 is the front of the queue. The input always describes a valid queue, and that queue is unique.
Examples
Input: people = [[5,0],[6,1],[4,2],[6,0]] Output: [[5,0],[6,0],[4,2],[6,1]]
The 4 has the 5 and a 6 in front of it; the second 6 has only the other 6 in front that is at least as tall.
Input: people = [[3,1],[3,0]] Output: [[3,0],[3,1]]
The person with k = 1 needs the other 3 in front.
Input: people = [[1,2],[2,1],[3,0]] Output: [[3,0],[2,1],[1,2]]
The heights must be in descending order to satisfy every k.
Constraints
- 1 <= people.length <= 2000
- 0 <= h_i <= 10^6
- 0 <= k_i < people.length
- The input always describes a queue that can be rebuilt
Approaches
- Baseline: fill the queue from the front — time O(n³), space O(n)
Follow-up
Inserting into a list costs O(n) each; with a Fenwick tree that finds the k-th free slot, placing people shortest first, the whole rebuild is O(n log n). The use cases go the other way (compute k from a queue) and mirror the question (count the people behind).
Related problems
Start free on Cariara · Coding problems · System design studio
