# My O(nlogn) solution with Binary Index Tree

• Just need to maintain the empty positions befor x ([1,x]) using BIT and the update operator's complexity is O(logn).

``````class Solution {
public:
int n, bit[1100];
int lowbit(int x) { return x & (-x); }
void update(int i, int x) {
while(i <= n) {
bit[i] += x;
i += lowbit(i);
}
}
int sum(int i) {
int ret = 0;
while(i) {
ret += bit[i];
i -= lowbit(i);
}
return ret;
}
int lb(int val) {
int lo = 1, hi = n;
while(lo <= hi) {
int mid = (lo + hi) >> 1;
int x = sum(mid);
if(x >= val) hi = mid - 1;
else lo = mid + 1;
}
return lo;
}
static bool cmp(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;
}
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
pair<int, int> ret[1100];
memset(bit, 0, sizeof(bit));
n = people.size();
for(int i = 2; i <= n; i++) update(i, 1);
sort(people.begin(), people.end(), cmp);
for(int i = 1; i <= n; i++) {
int pos = lb(people[i-1].second+1);
update(pos, -1);
ret[pos-1].first = people[i-1].first;
ret[pos-1].second = people[i-1].second;
}
people.clear();
for(int i = 1; i <= n; i++) people.push_back(ret[i]);
return people;
}
};
``````

• Actually your complexity is O(nlognlogn). You used both binary search and binary indexed tree.

• Can you explain your algorithm?

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