Queue Reconstruction by Height

Explanation & Solution

Description

You are given an array of people, where people[i] = [h_i, k_i] represents the height h_i of the i-th person and k_i is the number of people in front of this person who have a height greater than or equal to h_i.

Reconstruct and return the queue so that each person is placed at a position consistent with their k_i value.

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 [5,0] has no one taller or equal in front. Person [7,0] also has no one taller in front. Person [5,2] has two people ([7,0] and [5,0] counted as >= 5) in front. And so on for each person.

Constraints

1 <= people.length <= 2000
0 <= h_i <= 10^6
0 <= k_i < people.length
It is guaranteed that the queue can be reconstructed

Approach

Greedy Techniques pattern

1. Sort People by Height Descending, Then k Ascending

Sort the array so that the tallest people come first
Among people with the same height, sort by k in ascending order
For [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]], the sorted order is [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]

2. Insert Each Person at Their k Index

Iterate through the sorted array and insert each person into a result list at position k
Since we process taller people first, inserting a shorter person later at index k does not disturb the relative ordering of the taller people already placed

3. Walk Through the Insertions

Insert [7,0] at index 0 → [[7,0]]
Insert [7,1] at index 1 → [[7,0],[7,1]]
Insert [6,1] at index 1 → [[7,0],[6,1],[7,1]]
Insert [5,0] at index 0 → [[5,0],[7,0],[6,1],[7,1]]
Insert [5,2] at index 2 → [[5,0],[7,0],[5,2],[6,1],[7,1]]
Insert [4,4] at index 4 → [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

4. Return the Result

The result list now satisfies the constraint for every person: exactly k people in front have height >= theirs

Key Insight

The greedy strategy works because taller people are placed first and are never displaced by shorter people. When a shorter person is inserted at index k, they only push taller-or-equal people to the right, which does not change those people's k counts. This guarantees correctness for every person in the final arrangement.

Time

O(n^2)sorting takes O(n log n), but each insertion into the result array can shift up to O(n) elements, totaling O(n^2)

Space

O(n)for the result array

Visualization

Input:

[7,0, 4,4, 7,1, 5,0, 6,1, 5,2]

—

Press ▶ or use ← → to step through

Pointer iPointer jProcessedDone

8 steps

Solution Code

Hand of Straights

Two City Scheduling