406. Queue Reconstruction by Height

Problem

406. Queue Reconstruction by Height

Solution

Based on discussion from HERE

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        const int n = people.size();
        vector<vector<int>> ret;
        sort(people.begin(), people.end());
        unordered_map<int, int> cnt;
        for(auto x:people)cnt[x[0]]++;
        for(int i=n-1;i>=0;--i)
        {
            auto this_one = people[i];
            auto h = this_one[0], v= this_one[1];
            ret.insert(ret.begin()+(v-cnt[h]+1) , this_one);
            cnt[h]-- ;
        }
        return ret;
    }
};

By using a smarter way, we can sort by (x[0], -x[1]), then we do not need cent.

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

Or we can write it in this way

class Solution {
    static bool comparator(vector<int>& a,vector<int>& b)
    {
        if(a[0]==b[0]) return a[1]<b[1];
        return a[0]>b[0];
    }
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        const int n = people.size();
        vector<vector<int>> ret;
        sort(people.begin(), people.end(),comparator);
        for(auto p: people)ret.insert(ret.begin()+p[1] , p);
        return ret;
    }
};

Python solution

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x:(x[0], -x[1]))
        res = []
        while people:
            h, v = people.pop()
            res.insert(v, [h, v])
        return res