Count of Smaller Numbers After Self

Problem

Count of Smaller Numbers After Self

Intuition

We can use MergeSort to count the number of smaller elements to the right of nums[i], because in every merge operation, which is to merge two sorted array, we can know how many elements will be added in front of some element.

Code

class Solution {
    class Node{
        int val, idInNums, preId, newId, ans;
        public Node(int v, int i){
            val = v;
            idInNums = i;
            ans = 0;
        }
    }
    private void mergeSort(Node[] nums, int L, int R){
        if(L < R){
            int mid = L + (R - L) / 2;
            mergeSort(nums, L, mid);
            mergeSort(nums, mid + 1, R);
            merge(nums, L, R);
        }
    }
    private void merge(Node[] nums, int L, int R){
        int mid = L + (R - L) / 2;
        for(int i = L; i <= mid; i ++){
            nums[i].preId = i;
        }
        for(int i = mid + 1; i <= R; i ++){
            nums[i].preId = i;
        }
        Node[] newNums = new Node[R - L + 1];
        int id = 0, i = L, j = mid + 1;
        while(i <= mid || j <= R){
            if((i <= mid && j <= R && nums[i].val <= nums[j].val) || (i <= mid && j > R)){
                nums[i].newId = id;
                newNums[id] = nums[i];
                i ++;
                id ++;
            } else {
                nums[j].newId = id;
                newNums[id] = nums[j];
                j ++;
                id ++;
            }
        }
        for(id = 0, i = L; i <= R; i ++, id ++){
            nums[i] = newNums[id];
            if(nums[i].newId - (nums[i].preId - L) > 0)
                nums[i].ans += nums[i].newId - (nums[i].preId - L);
        }
    }
    public List<Integer> countSmaller(int[] nums) {
        int N = nums.length;
        Node[] nodes = new Node[N];
        for(int i = 0; i < N; i ++){
            nodes[i] = new Node(nums[i], i);
        }
        mergeSort(nodes, 0, N - 1);
        List<Integer> ans = Arrays.asList(new Integer[N]);
        for(int i = 0; i < N; i ++){
            ans.set(nodes[i].idInNums, nodes[i].ans);
        }
        return ans;
    }
}