Reverse Pairs

hard array divide and conquer merge sort

Problem

Count pairs (i, j) with i < j and nums[i] > 2 · nums[j].

Inputnums = [1,3,2,3,1]

Output2

Sort each half; cross-half counting then a merge step.

nums

def reverse_pairs(nums):
    def merge_sort(lo, hi):
        if lo >= hi: return 0
        mid = (lo + hi) // 2
        cnt = merge_sort(lo, mid) + merge_sort(mid+1, hi)
        j = mid + 1
        for i in range(lo, mid + 1):
            while j <= hi and nums[i] > 2 * nums[j]: j += 1
            cnt += j - (mid + 1)
        nums[lo:hi+1] = sorted(nums[lo:hi+1])
        return cnt
    return merge_sort(0, len(nums) - 1)

function reversePairs(nums) {
  function ms(lo, hi) {
    if (lo >= hi) return 0;
    const mid = (lo + hi) >> 1;
    let cnt = ms(lo, mid) + ms(mid + 1, hi);
    let j = mid + 1;
    for (let i = lo; i <= mid; i++) {
      while (j <= hi && nums[i] > 2 * nums[j]) j++;
      cnt += j - (mid + 1);
    }
    const merged = nums.slice(lo, hi + 1).sort((a, b) => a - b);
    for (let k = 0; k < merged.length; k++) nums[lo + k] = merged[k];
    return cnt;
  }
  return ms(0, nums.length - 1);
}

class Solution {
    public int reversePairs(int[] nums) { return ms(nums, 0, nums.length - 1); }
    int ms(int[] a, int lo, int hi) {
        if (lo >= hi) return 0;
        int mid = (lo + hi) >>> 1;
        int cnt = ms(a, lo, mid) + ms(a, mid + 1, hi);
        int j = mid + 1;
        for (int i = lo; i <= mid; i++) {
            while (j <= hi && a[i] > 2L * a[j]) j++;
            cnt += j - (mid + 1);
        }
        int[] tmp = Arrays.copyOfRange(a, lo, hi + 1);
        Arrays.sort(tmp);
        for (int k = 0; k < tmp.length; k++) a[lo + k] = tmp[k];
        return cnt;
    }
}

int ms(vector& a, int lo, int hi) {
    if (lo >= hi) return 0;
    int mid = (lo + hi) / 2;
    int cnt = ms(a, lo, mid) + ms(a, mid + 1, hi);
    int j = mid + 1;
    for (int i = lo; i <= mid; i++) {
        while (j <= hi && (long long)a[i] > 2LL * a[j]) j++;
        cnt += j - (mid + 1);
    }
    sort(a.begin() + lo, a.begin() + hi + 1);
    return cnt;
}
int reversePairs(vector& nums) { return ms(nums, 0, nums.size() - 1); }

Explanation

We need to count pairs where an earlier number is more than double a later one. Checking every pair takes n^2 time, but we can fold the counting into a modified merge sort to get it much faster.

Merge sort already splits the array into halves, sorts each, and merges them. The trick here is that before we merge a left half and a right half (both now sorted), we count the cross pairs — pairs where i is in the left and j is in the right with nums[i] > 2 * nums[j].

Because both halves are sorted, we use a two-pointer sweep. For each i in the left half, we advance j in the right half while nums[i] > 2 * nums[j]. Every j we passed forms a valid pair, so we add j - (mid + 1) to the count. Since nums[i] only grows, j never has to move backward.

Example: nums = [1,3,2,3,1]. The qualifying pairs are (3, 1) using the second value 3 and the final 1, and one more such pair, giving a total of 2. These get tallied during the merge steps as the halves combine.

Each level of the recursion does linear counting and the recursion is log n deep, so the whole approach runs in about n log n time instead of n^2.

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