Queue Reconstruction by Height — Greedy Sort + Insert

Problem

People described by [height, k] where k = number of people in front with height >= theirs. Reconstruct the queue.

Approach — Sort + Insert at Index

Sort by height descending (taller first), ties by k ascending. Insert each person at position k in result list.

Inserting taller people first means shorter people's k values are unaffected.

Time: O(n²) insert | Space: O(n)

Solutions

Python

class Solution:
    def reconstructQueue(self, people: list[list[int]]) -> list[list[int]]:
        people.sort(key=lambda x:(-x[0],x[1]))
        result=[]
        for p in people: result.insert(p[1],p)
        return result

C++

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people){
        sort(people.begin(),people.end(),[](auto& a,auto& b){return a[0]>b[0]||(a[0]==b[0]&&a[1]<b[1]);});
        vector<vector<int>> res;
        for(auto& p:people) res.insert(res.begin()+p[1],p);
        return res;
    }
};

Complexity

Time: O(n²) | Space: O(n)