Given a shuffled list of people, each described as (height, k) where k counts the people standing in front of them with height at least as tall, the machine must rebuild the original queue order. The reconstruction is unique for valid input.
The key insight is to insert people in descending height order. A shorter person never changes the k-value of a taller person, because the count only includes people at least as tall. So once the machine has placed everyone taller, each remaining person's k is simply the index where they belong in the queue built so far.
The approach runs in three steps. First, sort by height descending, breaking ties so that equal heights with smaller k come first. Second, walk the sorted list, inserting each person into the result list at exactly index k. Third, return the built queue. Time is O(n^2) because list insertion shifts elements, and space is O(n).
The trickiest edge case is equal heights: two people of the same height count each other, so the tie-break must insert the smaller k first. Sorting as (-height, k) does this automatically, guaranteeing that a later same-height person is inserted behind the earlier one without corrupting anyone's count.
def reconstructQueue(people):
people.sort(key=lambda p: (-p[0], p[1]))
queue = []
for h, k in people:
queue.insert(k, [h, k])
return queue