DSA problem
Queue Reconstruction by Height
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] = [h_i, k_i] represents the i-th person of height h_i with exactly k_i other people in front who have a height greater than or equal to h_i. 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] = [h_j, k_j] is the attributes of the j-th person in the queue.
A brute-force search over all n! permutations is hopeless even for moderate n. The structural fact that unlocks a greedy approach is this: once people taller-or-equal than a given person have been placed, inserting that person somewhere into the existing sequence does not change anyone's k_i value, because all the smaller people that will be inserted later are invisible to the taller ones' k count.
So the order in which we should insert people is "tallest first, breaking ties by smaller k_i first". Sort people in descending order of height; for equal heights, ascending order of k_i. Now process people one by one and insert each at position k_i in a growing list. Because everyone already in the list is at least as tall as the current person, inserting at index k_i automatically guarantees k_i taller-or-equal people in front.
This trades the brute combinatorial search for a sort plus n array insertions: O(n log n) to sort and O(n^2) worst-case for the inserts (each insert into the middle of an array shifts O(n) elements). It is the standard greedy reconstruction and is simple to argue correct by induction on insertion order.
Examples
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]]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]]people = [[1,0]][[1,0]]Constraints
- 1 <= people.length <= 2000
- 0 <= h_i <= 10^6
- 0 <= k_i < people.length
- It is guaranteed that the queue can be reconstructed.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.