LeetCode #406 Queue Reconstruction by Height
Problem
Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.
Note:
The number of people is less than 1,100.
Example
Input:
[[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]]
Solution
Look at the shortest person in people, you will find that its k number is just equal to correct position in result. By this observation, we can sort people first and insert each person into its corresponding position.
Complexity
The for loop on line 5 costs O(n) time if n denotes to the count of people. And each del and insert operation of people list will also cost O(n) time. Thus its time complexity is O(n²). And it’s trivial that it only needs O(1) extra space.
Edit
Thanks correction from Jason C. Huang. Because of enumerate on line 5, it also allocates O(n) extra space. So its space complexity should be O(n). But we can make code more simpler as follow:
