406. Queue Reconstruction by Height

Approach 1: Greedy!

a greedy algorithm repeatedly makes a locally best choice or decision, but ignores the effects of the future.

class Solution(object):
    def reconstructQueue(self, people):
        """
        https://leetcode.com/problems/queue-reconstruction-by-height/description/
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        people.sort(key=lambda x: (-x[0], x[1]))
        ret = []
        for i in range(len(people)):
            # print(res)
            ret.insert(people[i][1], people[i])
        return ret

We first sort the list people, in the order of decreasing height and if multiple people are of the same height, we'll sort them in increasing order of the number of people in front of them. Then for each person [i,j], their index in people_sorted is larger than or equal to j. Hence to obtain the final results, we just need to construct an empty list res, and starting from the left, insert each element [i,j] in people_sorted to position j in res

(Latter insertions of [i',j'] won't affect j because either i' < i, or i' == i and j' > j)

Uncomment the print statement to see it in action every iteration

Time Complexity: O(N^2) [Insertion is O(N)]

Space Complexity: O(N)