Queue Reconstruction by Height
MediumMathSortingQueue
Description
People are described by (h, k) where h is height and k is the number of people in front with height >= h. Reconstruct and return the queue.
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]]Explanation:
Sorted by height desc, insert by k.
Input:
people = [[1,0]]Output:
[[1,0]]Explanation:
With only one person of height 1 with 0 people taller in front, the queue contains just that single person.
Input:
people = [[6,0],[3,1],[8,0],[4,2],[9,0],[5,3]]Output:
[[6,0],[3,1],[8,0],[4,2],[9,0],[5,3]]Explanation:
Sort by height descending: [9,0],[8,0],[6,0],[5,3],[4,2],[3,1]. Insert each at index k: [9,0]→[[9,0]], [8,0]→[[8,0],[9,0]], [6,0]→[[6,0],[8,0],[9,0]], [5,3]→[[6,0],[8,0],[9,0],[5,3]], [4,2]→[[6,0],[8,0],[4,2],[9,0],[5,3]], [3,1]→[[6,0],[3,1],[8,0],[4,2],[9,0],[5,3]].
Constraints
- •
1 ≤ people.length ≤ 2000
Ready to solve this problem?
Practice solo and sharpen your skills for technical interviews.