406. Queue Reconstruction by Height

Problem

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.

Deploying React App on GitHub

Beginner’s Guide: Hash Tables

Uniqlo Blocktech Parkas #camping read here: https://t.co/GdRs9rI3hg

Fetching Script Tags and Attributes from String

Animating React component using React Framer Motion

Combining ZeroMQ with Vue.js

Backtracking

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

Introduction to Application Frameworks

S.O.L.I.D Principles

Spring Boot Initializer

Installing odoo v14/v15 on Ubuntu 20.04 VMWare