Queue Reconstruction by Height — LeetCode 406 Python Solution

The 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 ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

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

Explanation

Person 0 has height 5 with no other people taller or the same height in front.

Python solution

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

Complexity

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 406. Queue Reconstruction by Height is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Related problems