My O(n*log(n)*log(n)) solution with Binary Indexed Tree and Binary Search.

• First, sort people from short to tall (if there is a tie, the one with larger position in the origin queue go first).
Then, we insert people one by one into the queue. For each person (h, k), we leave k blank positions on the left.
So, a O(n^2) solution comes very naturally:

``````class Solution {

struct Less {
bool operator()(const pair<int,int> &a, const pair<int, int> &b) {
if (a.first != b.first) return a.first < b.first;
return a.second > b.second;
}
};

public:
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
int n = people.size();
vector<pair<int, int>> ans(n);
vector<bool> occ(n);

sort(people.begin(), people.end(), Less());

for (int j = 0; j < n; ++j) {
pair<int, int> &p = people[j];

int cnt = 0;
for (int i = 0; i < n; ++i) {
if (!occ[i]) {
if (cnt == p.second) {
ans[i] = p;
occ[i] = true;
break;
} else {
++cnt;
}
}
}
}

return ans;
}
};
``````

The insertion takes O(n) in the above solution.
And actually we can do better with Binary Indexed Tree and binary search.

``````class Solution {

struct Less {
bool operator()(const pair<int,int> &a, const pair<int, int> &b) {
if (a.first != b.first) return a.first < b.first;
return a.second > b.second;
}
};

public:
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
int n = people.size();
vector<pair<int, int>> ans(n);
vector<bool> occ(n);

sort(people.begin(), people.end(), Less());
initBIT(n);

for (int j = 0; j < n; ++j) {
pair<int, int> &p = people[j];

int lo = 0, hi = n;
while (lo < hi) {
int mid = (lo + hi) / 2;
cnt = query(mid+1, n);
if (mid - cnt < p.second) {
lo = mid + 1;
} else {
hi = mid;
}
}
insertToBIT(hi+1, n);
ans[hi] = p;
}

return ans;
}

private:
void initBIT(int n) {
mBIT.resize(n+1);
}
void insertToBIT(int i, int n) {
int j = i;
while (j <= n) {
mBIT[j]++;
j += (j&-j);
}
}
int query(int i, int n) {
int cnt = 0;
int j = i;
while (j > 0) {
cnt += mBIT[j];
j -= (j&-j);
}
return cnt;
}
vector<int> mBIT;
};
``````

• Excellent solution. Best one in BIT solns for this problems
vector<bool> occ(n) seems not used in your code.

I write my version based on yours.

``````    typedef pair<int,int> p;
vector<int> tree;
int n;
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
n = people.size();
tree.resize(n+1, 0);
sort(people.begin(), people.end(), [](const p&a, const p&b){
return a.first < b.first || a.first == b.first && a.second > b.second;
});
vector<p> ans(n);
for(int i = 0; i < n; i++) update(i, 1);
for(int i = 0; i < n; i++) {
auto& p = people[i];
int start = 0, end = n-1;
while(start < end) {
int mid = start + (end - start)/2;
if(query(mid) <= p.second) start = mid + 1;
else end = mid;
}
ans[start] = p;
update(start, -1);
}
return ans;
}
void update(int i, int val) {
for(++i; i <= n; i += i&(-i)) {
tree[i] += val;
}
}
int query(int i) {
int ans = 0;
for(++i; i > 0; i -= i&(-i)) {
ans += tree[i];
}
return ans;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.