315. Count of Smaller Numbers After Self

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.

Solution

For leetcode 315, applying the sequential recurrence relation (with j fixed), the subproblem C reads: find the number of elements out of visited ones that are smaller than current element, which involves searching on "dynamic searching space"; applying the partition recurrence relation, we have a subproblem C: for each element in the left half, find the number of elements in the right half that are smaller than it, which can be embedded into the merging process by noting that these elements are exactly those swapped to its left during the merging process.

class Solution {
        
    int[] count;
    public List<Integer> countSmaller(int[] nums) {
        
        int len = nums.length;
        count = new int[len];
        int[] indexes = new int[len];
        for(int i = 0; i < len ; i++){
            indexes[i] = i;
        }
        mergeSort(nums, indexes, 0, len-1);
        return Arrays.stream(count).boxed().collect(Collectors.toList());
    }
    
    public void mergeSort(int[] nums, int[] indexes, int from, int end){
        
        //do remember to add this exit condition
        if(end <= from){
            return;
        }
        
        int mid = from + (end - from)/2;
        mergeSort(nums, indexes, from, mid);
        mergeSort(nums, indexes, mid+1, end);
        merge(nums, indexes, from, mid, mid+1, end);
    }
    
    public void merge(int[] nums, int[] indexes, int lstart, int lend, int rstart, int rend)    {
        int rightCount = 0;
        int from = lstart;
        int[] result = new int[rend-lstart+1];
        int i = 0;
        while(lstart <= lend && rstart <= rend){
            if(nums[indexes[lstart]] > nums[indexes[rstart]]){
                result[i++] = indexes[rstart];
                rightCount++;
                rstart++;
            }
            // ==的case不算是滿足smaller的條件，所以要走這個case
            else if(nums[indexes[lstart]] <= nums[indexes[rstart]])             {
                //因為mege時可能會再次計算到同個點，所以用+=
                count[indexes[lstart]] += rightCount;
                result[i++] = indexes[lstart];
                lstart++;
            }
        }
        while(lstart > lend && rstart <= rend){
            result[i++] = indexes[rstart++];
        }
        
        while(lstart <= lend && rstart > rend){
            //do remeber to add the rightCounter 
            //whenever a left side note is assigned
            count[indexes[lstart]] += rightCount;
            result[i++] = indexes[lstart++];
        }
        for(i = 0; i < result.length; i++){
            indexes[from++] = result[i];
        }
        
    }
    
}