https://leetcode.com/problems/queue-reconstruction-by-height

The idea of my solution is following: let us find the first person in our queue, how can we do it? First, it should be a person with k=0, and also it should be a person with minumum height among all these people. What happened, when we found this person? We need to update values of k for all persons after, for which heights were less or equal than this person. However in this way we modify our data, so I use line people = [[x,y,y] for x, y in people] to reconstrunct our data: 0-th index is for height, 2-nd for modified k and 1-st for original k.

Let us go through example and see how it works, people = [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]:

  1. Modify data: [[7, 0, 0], [4, 4, 4], [7, 1, 1], [5, 0, 0], [6, 1, 1], [5, 2, 2]]
  2. Choose the smallest element with k_modified = 0: this is [5,0,0]: we pop this element and modify the rest: [[7, 0, 0], [4, 4, 3], [7, 1, 1], [6, 1, 1], [5, 2, 1]], where we changed values of k_modified for [4, 4, 4] and [5, 2, 2]
  3. Choose the smallest new element, which is [7, 0, 0] and modify people = [[4, 4, 2], [7, 1, 0], [6, 1, 0], [5, 2, 0]]
  4. Choose the smallest new element, which is [5, 2, 0] and modify people = [[4, 4, 1], [7, 1, 0], [6, 1, 0]]
  5. Choose the smallest new element, which is [6, 1, 0] and modify people = [[4, 4, 0], [7, 1, 0]]
  6. Choose the smallest new element, which is [4, 4, 0] and modify people = [[7, 1, 0]]
  7. Choose the smallest new element, which is [7, 1, 0] and modify people = []

Complexity. Time complexity is O(n^2), because we do n iterations, and find minimum and modify at most n elements on each iteration. Space comlexity is O(n).

class Solution:
    def reconstructQueue(self, people):
        people = [[x,y,y] for x, y in people]
        
        out = []
        while people:
            ind = people.index(min(people,key=lambda x: (x[2],x[0])))
            out.append(people.pop(ind))
            people = [[x,y,z - (x <= out[-1][0])] for x,y,z in people ]
    
        return [[x,y] for x,y,z in out]

Remarks

Actually, there is better solution with $\mathcal{O}(n\log n)$ complexity, using either segment tree or binary indexed tree.

If you like the solution, you can upvote it on leetcode discussion section: Problem 0406