Hex.*

LC406 - Queue Reconstruction by Height

Posted on In
Leetcode: 128/2658 (53+61+14)

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 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 <= 2000
0 <= hi <= 106
0 <= ki < people.length
It is guaranteed that the queue can be reconstructed.

Solution

  • Sort people by height in descending order, same height by location in ascending order
  • Inserted by position value from big to small, because the big one is inserted first, the current position is the position of the inserted column.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# O(n^2) time | O(logn) space
class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x:(-x[0], x[1]))
        res = []
        
        for h, idx in people:
            res.insert(idx, (h, idx))
        return res

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

Note

Time complexity: O(n^2), where n is the length of people, requires O(nlogn) sorting, and then takes O(n^2) time to traverse each person into the queue

1
2
3
4
5
6
7
8
people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
ans = []
for i in people:
    ans[i[1]:i[1]] = [i]
print(ans)

## insert
ans[i[1]:i[1]] = [i] == ans.insert(i[1], i)