Reverse Pairs [Hard] — Merge Sort with Cross-Half Counting

Problem Statement

Count reverse pairs: pairs (i,j) where i < j and nums[i] > 2*nums[j].

Input: [1,3,2,3,1] → Output: 2
Input: [2,4,3,5,1] → Output: 3

Intuition

Modified merge sort. After recursively sorting both halves, count pairs across the halves (left value > 2 × right value) using two pointers before merging. Then merge normally.

Solutions

Python

def reversePairs(nums: list[int]) -> int:
    def merge_sort(arr):
        if len(arr) <= 1:
            return arr, 0
        mid = len(arr) // 2
        left, lc = merge_sort(arr[:mid])
        right, rc = merge_sort(arr[mid:])
        count = lc + rc
        # Count cross pairs
        j = 0
        for x in left:
            while j < len(right) and x > 2 * right[j]:
                j += 1
            count += j
        # Merge
        merged = []
        i = k = 0
        while i < len(left) and k < len(right):
            if left[i] <= right[k]: merged.append(left[i]); i += 1
            else: merged.append(right[k]); k += 1
        merged.extend(left[i:]); merged.extend(right[k:])
        return merged, count

    _, total = merge_sort(nums)
    return total

C++

int count=0;
void mergeCount(vector<int>& nums, int l, int r) {
    if(l>=r) return;
    int mid=(l+r)/2;
    mergeCount(nums,l,mid); mergeCount(nums,mid+1,r);
    int j=mid+1;
    for(int i=l;i<=mid;i++){
        while(j<=r&&(long long)nums[i]>2LL*nums[j]) j++;
        count+=j-(mid+1);
    }
    inplace_merge(nums.begin()+l,nums.begin()+mid+1,nums.begin()+r+1);
}
int reversePairs(vector<int>& nums) {
    count=0; mergeCount(nums,0,nums.size()-1); return count;
}

Complexity

Time: O(n log n)
Space: O(n)