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


  • 1
    M

    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;
    };
    

  • 0
    C

    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;
        }
    

Log in to reply
 

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