315. Count of Smaller Numbers After Self

• Difficulty: Hard

• Topics: Binary Search, Divide and Conquer, Sort, Binary Indexed Tree, Segment Tree

• Similar Questions:

  • Count of Range Sum

  • Queue Reconstruction by Height

  • Reverse Pairs

Problem:

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Input: [5,2,6,1]
Output: [2,1,1,0] 
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Solutions:

class Solution {
public:
    class BIT {
        public:
            BIT(int upper) {
                nums.resize(upper + 1);
                upperBound = upper;
            }

            void add(int index) {
                while (index <= upperBound) {
                    ++nums[index];
                    index += lowerBit(index);
                }
            }

            int query(int index) {
                int sum = 0;
                while (index > 0) {
                    sum += nums[index];
                    index -= lowerBit(index);
                }
                return sum;
            }

            inline int lowerBit(int i) {
                return i & (-i);
            }

        private:
            int upperBound;
            vector<int> nums;
    };


    vector<int> countSmaller(vector<int>& nums) {
        if (nums.size() == 0)   return {};
        int smallest = *min_element(nums.begin(), nums.end());
        int offset = 0;
        if (smallest < 1) {
            offset = 1 - smallest; // offset is 1 not 0;
        }

        int upper = *max_element(nums.begin(), nums.end());
        BIT bit(upper+offset);
        int n = nums.size();
        vector<int> ret(n);
        for (int i = n - 1; i >= 0; --i) {
            int val = nums[i] + offset;
            ret[i] = bit.query(val-1); // query is tricky!
            bit.add(val);
        }

        return ret;
    }

};