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].

Test Cases

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,-1]
Output: [0,0]

Solution

class Solution {
public:
    void merge(vector<int> &count, vector<pair<int, int> > &v, int left, int mid, int right) {
        vector<pair<int, int> > tmp(right-left+1);
        int i = left;
        int j = mid+1;
        int k = 0;

        while (i <= mid && j <= right) {
            if (v[i].first <= v[j].first) {
                tmp[k++] = v[j++];
            }
            else {
                count[v[i].second] += right - j + 1;
                tmp[k++] = v[i++];
            }
        }
        while (i <= mid) {
            tmp[k++] = v[i++];
        }
        while (j <= right) {
            tmp[k++] = v[j++];
        }
        for (int i = left; i <= right; i++)
            v[i] = tmp[i-left];
    }

    void mergeSort(vector<int> &count, vector<pair<int, int> > &v, int left, int right) {
        if (left >= right)
            return;

        int mid = left + (right-left)/2;
        mergeSort(count, v, left, mid);
        mergeSort(count, v, mid+1, right);
        merge(count, v, left, mid, right);
    }

    vector<int> countSmaller(vector<int>& nums) {
        int N = nums.size();

        vector<pair<int, int> > v(N);
        for (int i = 0; i < N; i++)
            v[i] = make_pair(nums[i], i);

        vector<int> count(N, 0);
        mergeSort(count, v, 0, N-1);

        return count;
    }
};
class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        Pair[] pairs = new Pair[n];
        for(int i=0; i<n; i++) {
            pairs[i] = new Pair(nums[i], i);
        }

        int[] count = new int[n];
        mergeSort(count, pairs, 0, n-1);
        List<Integer> result = new ArrayList<>();
        for(int c: count) result.add(c);
        return result;
    }

    private void mergeSort(int[] count, Pair[] pairs, int left, int right) {
        if (left >= right) return;
        int mid = left + (right-left)/2;
        mergeSort(count, pairs, left, mid);
        mergeSort(count, pairs, mid+1, right);
        merge(count, pairs, left, mid, right);
    }

    private void merge(int[] count, Pair[] pairs, int left, int mid, int right) {
        Pair[] temp = new Pair[right-left+1];
        int i=left, j=mid+1, k=0;
        while(i <= mid && j<= right) {
            if (pairs[i].val <= pairs[j].val) {
                temp[k++] = pairs[j++];
            } else {
                count[pairs[i].pos] += right - j + 1;
                temp[k++] = pairs[i++];
            }
        }
        while(i <= mid) {
            temp[k++] = pairs[i++];
        }
        while(j <= right) {
            temp[k++] = pairs[j++];
        }
        for(i=left; i<= right; i++) {
            pairs[i] = temp[i-left];
        }
    }
}

class Pair {
    int val;
    int pos;

    public Pair(int val, int pos) {
        this.val = val;
        this.pos = pos;
    }
}
Time Complexity: O(nlogn)
Space Complexity: O(n)