258. Reverse Pairs

During merge sort, before merging two sorted halves, count pairs where a left element is more than twice a right element. Sorted halves let a two-pointer sweep count these in linear time.

Count while sorting

A brute-force pair check is O(n²). Instead, fold the counting into merge sort: for each recursive split into a sorted left half and sorted right half, count pairs (i, j) with i in the left, j in the right, and nums[i] > 2 * nums[j].

Because both halves are sorted, a two-pointer sweep counts them in O(n): advance j while left[i] > 2 * right[j]; all j up to that point pair with i (and with every larger left element too).

sortCount(lo, hi):
    if segment tiny: return 0
    count = sortCount(left) + sortCount(right)
    j = mid
    for i in left: while j<hi and nums[i] > 2*nums[j]: j++
                   count += j - mid
    sort the segment; return count

Worked example

[1,3,2,3,1] → reverse pairs (3,1) at indices (1,4) and (3,4) → 2.

Complexity

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

import java.util.Arrays;

class Solution {
    private int[] nums;

    public int reversePairs(int[] nums) {
        this.nums = nums;
        return sortCount(0, nums.length);
    }

    private int sortCount(int lo, int hi) {
        if (hi - lo <= 1) return 0;
        int mid = (lo + hi) / 2;
        int count = sortCount(lo, mid) + sortCount(mid, hi);
        int j = mid;
        for (int i = lo; i < mid; i++) {
            while (j < hi && (long) nums[i] > 2L * nums[j]) j++;
            count += j - mid;
        }
        int[] seg = Arrays.copyOfRange(nums, lo, hi);
        Arrays.sort(seg);
        System.arraycopy(seg, 0, nums, lo, seg.length);
        return count;
    }
}