Queue Reconstruction by Height Problem

Queue Reconstruction by Height Problem — ExecCode Medium DSA Practice

Solve the Queue Reconstruction by Height problem on ExecCode. Free online medium DSA practice in Greedy. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Description 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 of height hi with exactly ki other people in front 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). Examples Example 1 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 0 has height 5 with no other people taller or the same height in front. Person 1 has height 7 with no other people taller or the same height in front. Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1. Person 3 has height 6 with one person taller or the same height in front, which is person 1. Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3. Person 5 has height 7 with one person taller or the same h…

Examples

Input people = [[9, 0], [7, 0], [5, 0], [6, 1], [3, 2], [2, 2], [1, 4], [8, 1]]; Output [[5, 0], [7, 0], [2, 2], [3, 2], [1, 4], [6, 1], [9, 0], [8, 1]]. Input people = [[5, 5], [5, 4], [5, 3], [5, 2], [5, 1], [5, 0]]; Output [[5, 0], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5]]. Input people = [[1, 0], [2, 0], [3, 0], [4, 0], [5, 0]]; Output [[1, 0], [2, 0], [3, 0], [4, 0], [5, 0]]

Constraints

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

Practice Queue Reconstruction by Height free on ExecCode. Browse DSA problems, topic map, and placement guides.