# 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`

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

## Jimmy Shen

Data Scientist/MLE/SWE @takemobi