O(nlogn) Binary Index Tree C++ solution


  • 9
    Y
    1. Sort by height, if height is equal, sort by second item
    
    2. Naive Algorithm:
       for each item in seq:
             find the new insert position and assign it to the item
    
    3. Case analysis:
        [4,4], [5,0], [5,2], [6,1], [7,0], [7,1], total 6 sorted items
        that means we must fill 6 blankets.     _ _ _ _ _ _ 
        (1)[4,4] means there are 4 items before it, since no other items less than it, so it must be at the 5th pos. 
        (2)[5,0] means there are 0 items before it, so it must be at the first pos.
        ......
        (6)same as before
        
       visualize process
       -----------------
    
         _      _      _      _      _      _
         _      _      _      _    [4,4]    _
       [5,0]    _      _      _    [4,4]    _
       [5,0]    _    [5,2]    _    [4,4]    _
       [5,0]    _    [5,2]  [6,1]  [4,4]    _
       [5,0]  [7,0]  [5,2]  [6,1]  [4,4]    _
       [5,0]  [7,0]  [5,2]  [6,1]  [4,4]  [7,1]
    
    4. Improved Algorithm
        for each item in seq:
             pos = find Kth avaliable position in newArray // K = item.second
             newArray[pos] = item
             used[pos] = true
    
       Implement find_Kth() method can be done in O(n), thus total complexity is O(n^2)
    
    5. Implement find_Kth() method in O(lgN*lgN) or O(lgN) use BIT
        (1)trick #1: to convert the former "fill blanket" to "range sum"
        (2)trick #2: if height[i] == height[i+1], we must delay the "convert" operation as below described
    
       visualize process
       -----------------
         1   1   1   1   1   1      // first initialize all position with 1
         1   1   1   1   0   1     // find [4,4] pos by calling find_Kth(4+1), pos = 5, and convert 1 to 0
         1   1   1   1   0   1     // find [5,0] pos by calling find_Kth(0+1), pos = 1, do not convert 1 to 0 
         0   1   0   1   0   1     // find [5,2] pos by calling find_Kth(2+1), pos = 3, and convert 1 to 0
         0   1   0   0   0   1     // find [6,1] pos by calling find_Kth(1+1), pos = 4, and convert 1 to 0
         0   1   0   0   0   1     // find [7,0] pos by calling find_Kth(0+1), pos = 2, do not convert 1 to 0 
         0   0   0   0   0   0     // find [7,1] pos by calling find_Kth(1+1), pos = 6, convert 1 to 0
    

    Dirty Code Below......
    Hope someone can post a nice and clean code.....

    class Solution {
    public:
        typedef pair<int,int> Node;
        vector<int> c;
        int n;
        vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
            int len = people.size();
            vector<Node> ans(len);
            vector<int> tmp(len+2,0);
            c = tmp;
            n = len;
            
            //initialize
            for(int i = 1; i <= n; i++)update(i,1);
            sort(people.begin(), people.end());
            
            int pre = -1;
            vector<int> preNum;
            
            for(int i = 0; i < len; i++)
            {
                //amotized O(1) operation
                if(people[i].first != pre)
                {
                    for(int j = 0; j < preNum.size(); j++)update(preNum[j],-1);
                    preNum.clear();
                        
                }
                int num = findKth(people[i].second+1);
                ans[num-1] = people[i];
                
                preNum.push_back(num);
                pre = people[i].first;
            }
            
            return ans;
            
        }
        
       //Binary Index Tree update
        void update(int idx, int val)
        {
            while(idx <= n)
            {
                c[idx] += val;
                idx += idx & -idx;
            }
        }
        
        //Binary Index Tree getSum [1, idx]
        int getsum(int idx)
        {
            int sum = 0;
            while(idx > 0)
            {
                sum += c[idx];
                idx -= idx & -idx;
            }
            return sum;
        }
        
        //find-Kth position, Here I use Binary-search, So complexity is O(lgN*lgN)
        int findKth(int k)
        {
            int l = 1, r = n, mid;
            while(l <= r)
            {
                mid = (l + r) >> 1;
                if(getsum(mid) >= k)r = mid - 1;
                else l = mid + 1;
            }
            return l;
        }
        
        bool static cmp(Node a, Node b)
        {
            if(a.first == b.first)return a.second < b.second;
            return a.first < b.first;
        }
    };
    
    
    //Another O(lgN) find_Kth implementaiton
    /*
    int find_kth(int k)
    {
        int cnt = 0, ans = 0;
        for(int i = 20; i >=0; i--)
        {
            ans += 1 << i;
            if(ans >= n || cnt + c[ans] >= k)ans -= 1 << i;
            else cnt += c[ans];
        }
        return ans + 1;
    }
    */
    

  • 2
    T

    It might be a little simpler if you order [5,2] before [5,0], because then insertion of [5,2] will not be affected by [5,0].


  • 0
    S

    Great solution! thanks for sharing


  • 0
    Y

    If there is a lot of 0 before an 1, and the sum will keep same for a continuous interval. We need to find the first one in this interval, who corresponds to 1(not occupied), but in the process of the binary search, it is not accurate to find that position.
    After locating an answer by binary search, if we search along to the left to find the leftmost one, it will be O(n) and it may cost TLE.

    One possible way to fix this is during the binary search, find the one where getsum(x) == k and getsum(x-1) == k-1 then return... I didn't really get why your answer is correct XD.


  • 0
    B

    if a.first==b.first, it should be sort as a.second>b.second.

    In your case analysis, we should put (5, 2) before (5, 0).


  • 0
    P

    said in O(nlogn) Binary Index Tree C++ solution:
    Very nice explanation....


  • 0
    Z

    It's such a pity that I can not upvote u twice. Nice solution!


  • 0
    K

    Here is my implementation for AIB

    class Solution {
        struct AIB
        {
            std::vector<int> data;
            std::vector<bool> flags;
            std::vector<int> aib;X
    
            AIB(int size)
            {
                data.resize(size);
                flags.resize(size, false);
                for (int i = 1; i <= size; ++i)
                    aib.push_back(i & -i);
            }
    
            void Insert(int e, int pos)
            {
                int i = 1, u = aib.size(), c = pos + 1;
                while (i <= u)
                {
                    int k = -1;
                    while (i <= u && aib[i - 1] <= c)
                    {
                        if (aib[i - 1] == c)
                        {
                            if (!flags[i - 1])
                            {
                                data[i - 1] = e;
                                flags[i - 1] = true;
                                while (i <= static_cast<int>(aib.size()))
                                {
                                    --aib[i - 1];
                                    i += i & -i;
                                }
                                return;
                            }
                            else
                                break;
                        }
                        k = i;
                        i += i & -i;
                    }
                    if (i <= u)
                        u = i - 1;
                    i = k;
                    c -= aib[i - 1];
                    i++;
                }
            }
        };
    public:
        vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
            std::sort(people.begin(), people.end(), [](const std::pair<int, int> &p1, const std::pair<int, int> &p2) {
                if (p1.first != p2.first)
                    return p1.first < p2.first;
                return p2.second < p1.second;
            });
            AIB aib(people.size());
            for (int i = 0; i < static_cast<int>(people.size()); ++i)
                aib.Insert(i, people[i].second);
            std::vector<std::pair<int, int>> ret;
            for (auto i : aib.data)
                ret.push_back(people[i]);
            return ret;
        }
    };
    

Log in to reply
 

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