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


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

Log in to reply
 

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