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 ith 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 jth person in the queue (queue[0] is the person at the front of the queue).
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 height in front, which is person 1. Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.
Example 2:
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]]
Constraints:
1 <= people.length <= 20000 <= hi <= 1060 <= ki < people.lengthIn this approach, we first sort the array of people. The sorting criteria should be descending order of height and ascending order of the number of people in front for the same height. After sorting, we iterate through the list and insert each person into a new list at the index corresponding to the number of people in front of them. This ensures that each person is placed correctly with regard to the number of taller or equally tall people in front.
This C solution sorts the list with a custom comparator and then builds the resulting queue by inserting each person at their k-th index. The qsort is used for sorting the list based on the height in descending order and the k-value in ascending order. We use an auxiliary array to store the reconstructed queue, shifting elements as needed during insertion to maintain order.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) due to the potential element shifting during insertion.
Space Complexity: O(1) additional space required.
Queue Reconstruction by Height | Leetcode #406 • Techdose • 27,581 views views
Watch 9 more video solutions →Practice Queue Reconstruction by Height with our built-in code editor and test cases.
Practice on FleetCode