Queue Reconstruction by Height

The key idea

Place the tallest people first. Sort by height descending (ties by k ascending), then insert each person at the index equal to their k. Because everyone already placed is taller or equal, that k counts exactly the people who must stand in front, so the index is correct and never shifts wrong.

Problem

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 i-th person, where hi is the height of the person and ki is the number of people in front of this person 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 j-th person in the queue (queue[0] is the person at the front of the queue).

Constraints

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

Examples

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]]

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]]

Complexity

Time: O(n^2) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →