Given an integer array nums, return an integer array counts where counts[i] is the number of smaller elements to the right of nums[i].

&nbsp;
Example 1:

Input: nums = [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.


Example 2:

Input: nums = [-1]
Output: [0]


Example 3:

Input: nums = [-1,-1]
Output: [0,0]


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 105
	-104 &lt;= nums[i] &lt;= 104


class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        # build the binary indexed tree
        num_buckets = 10 ** 4 + 10 ** 4 + 1 # 10**4 negative + 10**4 positive numbers + bucket at 0
        tree = [0] * (num_buckets + 1) # add 1 because binary indexed tree data starts at index 1

        result = [0] * len(nums)

        # iterate from right to left
        for result_index in range(len(nums) - 1, -1, -1):
            n = nums[result_index]
            # add 10**4 to n to account for negative numbers
            i = n + 10 ** 4

            # convert to 1-based index for the tree
            i += 1
            # perform range sum query of buckets [-inf, n-1], where n is current number
            # because we want n - 1 for range sum query of [-inf, n-1], not n, subtract 1 from i:
            i -= 1

            val = 0
            while i != 0:
                val += tree[i]
                # get parent node by subtracting least significant set bit
                i -= i & -i

            result[result_index] = val

            # update the binary indexed tree with new bucket
            i = n + 10 ** 4
            i += 1
            while i < len(tree):
                tree[i] += 1
                # get next node to update by adding the least significant set bit
                i += i & -i

        return result
class Solution {    
    public List<Integer> countSmaller(int[] nums) {
        int min = 20001;
        int max = -1;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        
        min--;
        int[] count = new int[max-min+1];
        Integer[] result = new Integer[nums.length];
        for (int i = nums.length-1; i >=0; i--) {
            int k = nums[i]-min-1;
            int c = 0;
            do {
                c += count[k];
                k -= (-k&k);
            } while (k > 0);
            result[i] = c;
            
            k = nums[i]-min;
            while (k < count.length) {
                count[k]++;
                k += (-k&k);
            }
        }
        
        return Arrays.asList(result);
    }
}
typedef struct _SmallerValueCount {
    _SmallerValueCount(const int &value, const int &originalIndex) :
        mValue(value), mOriginalIndex(originalIndex) {}
    
    int mValue = 0;
    int mOriginalIndex = 0;
} SmallerValueCount;

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<SmallerValueCount> convertedNums;
        convertedNums.reserve(nums.size());

        for (int i = 0; i < nums.size(); ++i)
            convertedNums.emplace_back(SmallerValueCount(nums[i], i));

        vector<int> smallerCounts(convertedNums.size(), 0);
        merge_sort(convertedNums, smallerCounts, 0, nums.size() - 1);

        return smallerCounts;
    }

    void merge_sort(vector<SmallerValueCount> &nums, vector<int> &smallerCounts, const int &left, const int &right) {
        if (left >= right)
            return;
        const auto mid = (left + right) / 2;
        merge_sort(nums, smallerCounts, left, mid);
        merge_sort(nums, smallerCounts, mid+1, right);
        merge(nums, smallerCounts, left, mid, right);
    }

    void merge(vector<SmallerValueCount> &nums, vector<int> &smallerCounts, const int &left, const int &mid, const int &right)
    {
        vector<SmallerValueCount> buffer;
        buffer.reserve(right - left + 1);

        int i = left, j = mid + 1;
        int smallerCount = 0;
        while (i <= mid && j <= right)
            if (nums[i].mValue > nums[j].mValue)
            {
                ++smallerCount;
                buffer.push_back(nums[j]);
                ++j;
            }
            else
            {
                smallerCounts[nums[i].mOriginalIndex] += smallerCount;
                buffer.push_back(nums[i]);
                ++i;
            }

        while (i <= mid)
        {
            smallerCounts[nums[i].mOriginalIndex] += smallerCount;
            buffer.push_back(nums[i]);
            ++i;
        }

        while (j <= right)
        {
            buffer.push_back(nums[j]);
            ++j;
        }

        std::move(std::begin(buffer), std::end(buffer), std::next(std::begin(nums), left));
    }

};
var countSmaller = function(nums) {
    if(nums===null || nums.length == 0) return []
    
    let N = nums.length
    const result = new Array(N).fill(0)
    const numsWithIdx = new Array(N).fill(0)
    
    for(let i = 0; i < nums.length; i++) {
        const curr = nums[i]
        
        numsWithIdx[i] = {val:curr, originalIdx: i}
    }

    divideAndConqueuer(0, nums.length - 1)
    
    const resultList = []
    result.forEach(el => resultList.push(el))
    
    return resultList

    function divideAndConqueuer(left, right) {
        if(left < right) {
            const mid = Math.floor(left + (right - left)/2)
            divideAndConqueuer(left, mid)
            divideAndConqueuer(mid+1, right)
            merge(left, mid, right)
        }
    }

    function merge(left, mid, right) {
        const leftLen = mid - left + 1
        const rightLen = right - mid
        
        let rightSmallers = 0

        const leftAux = new Array(leftLen).fill(0)
        const rightAux = new Array(rightLen).fill(0)


        for(let i = 0; i < leftLen; i++) {
            leftAux[i] = numsWithIdx[left+i]
        }


        for(let i = 0; i < rightLen; i++) {
            rightAux[i] = numsWithIdx[mid+1+i]
        }


        let leftPointer = 0
        let rightPointer = 0
        let insertAtPointer = left

        while(leftPointer < leftLen && rightPointer < rightLen) {
            if(leftAux[leftPointer].val <= rightAux[rightPointer].val) {
                
                result[leftAux[leftPointer].originalIdx] += rightSmallers  
                numsWithIdx[insertAtPointer++] = leftAux[leftPointer++]
                
            } else {
                numsWithIdx[insertAtPointer++] = rightAux[rightPointer++]                
                rightSmallers++
            }
        }


        while(rightPointer < rightLen) {
                numsWithIdx[insertAtPointer++] = rightAux[rightPointer++]                            
        }
        
        while(leftPointer < leftLen) {
                result[leftAux[leftPointer].originalIdx] += rightSmallers  
                numsWithIdx[insertAtPointer++] = leftAux[leftPointer++]            
        }

    }
};
Count of Smaller Numbers After Self