406. Queue Reconstruction by Height

Problem Statement

link: LeetCode.cn LeetCode

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:

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

Solution Approach

To reconstruct the queue, we first sort the people based on their height in descending order and their k value in ascending order. Then, we iterate through the sorted list and insert each person at the index specified by their k value.

Algorithm

1. Sort the people list in descending order of height (hi) and ascending order of k value using a custom sorting key.
2. Initialize an empty list res to store the reconstructed queue.
3. Iterate through each person in the sorted list: Insert the person into the res list at the index specified by their k value.
4. Return the reconstructed queue res.

Implement

    class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
      people.sort(key= lambda x : (-x[0], x[1]))
      res = []
      for p in people:
        res.insert(p[1], p)
      return res
    
       

    
    

Twitter  facebook  Email