493. Reverse Pairs

Link

Solution

Break down the main problem into subproblems and add on the result between those subproblems.

T(i, j) = T(i, m) + T(m + 1, j) + C where m = (i+j)/2, i.e., subarray nums[i, j] will be further partitioned into two parts and C denotes the results from combining the two parts. We will call this partition recurrence relation.

 public int reversePairs(int[] nums) {
        int N = nums.length;
        
        return getReversePairCount(nums, 0, N-1);
    }
    
    public int getReversePairCount(int[] nums, int start, int end){
        if(start >= end) return 0;
        
        int mid = start + (end-start)/2;
        
        int ans = getReversePairCount(nums, start, mid) + getReversePairCount(nums, mid+1, end);
       int i = start, j = mid+1;
        
        while(i <= mid){
            
            while(j <= end && nums[i]/2.0 > nums[j]) j++;
            ans += j - mid - 1;
            i++;
        }
        //Arrays.sort(nums, start, end); // less-effiecient way
        mergeSort(nums, start, mid, end);
        return ans;
    }
    
    
    public void mergeSort(int[] nums, int start, int mid, int end){
        int[] ans = new int[end-start+1];
        int i = start, j = mid+1, k = 0;
        while(i <= mid && j <= end){
            if(nums[i] < nums[j]){
                ans[k++] = nums[i++];
            }
            else{
                ans[k++] = nums[j++];
            }
        }    
        while(i <= mid){
            ans[k++] = nums[i++];
        }
        
        while(j <= end){
            ans[k++] = nums[j++];
        }
        k = 0;
        i = start;
        while(i <= end){
            nums[i++] = ans[k++];
        }
    }