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:

Given nums = [5, 2, 6, 1]

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.
Return the array [2, 1, 1, 0].

Solution

public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int[] indice = new int[nums.length];
        Integer[] ans = new Integer[nums.length];
        for(int i = 0; i < nums.length; i++) {
            indice[i] = i;
            ans[i] = 0;
        }

        splitMerge(nums, indice, ans, 0, nums.length-1);
        return Arrays.asList(ans);
    }

    public void splitMerge(int[] nums, int[] indice, Integer[] ans, int i, int j) {
        if(i >= j) return;

        int mid = (i + j) / 2;
        splitMerge(nums, indice, ans, i, mid);
        splitMerge(nums, indice, ans, mid+1, j);

        int sortedNum[] = new int[j - i + 1];
        int sortedIdx[] = new int[j - i + 1];

        // merge [i, mid] [mid+1, j] and modify ans
        int idx1 = i;
        int idx2 = mid+1;
        int cnt = 0;
        int increment = 0;
        while(idx1 != mid+1 || idx2 != j+1) {
            if(idx1 == mid + 1) {
                sortedNum[cnt] = nums[idx2]; 
                sortedIdx[cnt] = indice[idx2];
                idx2++;
                increment++;
            } else if(idx2 == j + 1) {
                sortedNum[cnt] = nums[idx1]; 
                sortedIdx[cnt] = indice[idx1];
                ans[indice[idx1]] += increment;
                idx1++;
            } else {
                if(nums[idx1] <= nums[idx2]) {
                    sortedNum[cnt] = nums[idx1]; 
                    sortedIdx[cnt] = indice[idx1];
                    ans[indice[idx1]] += increment;
                    idx1++;
                } else {
                    sortedNum[cnt] = nums[idx2]; 
                    sortedIdx[cnt] = indice[idx2];
                    idx2++;
                    increment++;
                }
            }
            cnt++;
        }

        for(int k = i; k <= j; k++) {
            nums[k] = sortedNum[k - i];
            indice[k] = sortedIdx[k - i];
        }
    }
}