Reverse Pairs

Given an integer array nums, return the number of reverse pairs in the array.

A reverse pair is a pair (i, j) where:

• 0 <= i < j < nums.length and
• nums[i] > 2 * nums[j].

Example 1:

Input: nums = [1,3,2,3,1] Output: 2 Explanation: The reverse pairs are: (1, 4) —> nums[1] = 3, nums[4] = 1, 3 > 2 * 1 (3, 4) —> nums[3] = 3, nums[4] = 1, 3 > 2 * 1

Example 2:

Input: nums = [2,4,3,5,1] Output: 3 Explanation: The reverse pairs are: (1, 4) —> nums[1] = 4, nums[4] = 1, 4 > 2 * 1 (2, 4) —> nums[2] = 3, nums[4] = 1, 3 > 2 * 1 (3, 4) —> nums[3] = 5, nums[4] = 1, 5 > 2 * 1

Constraints:

• 1 <= nums.length <= 5 * 104
• -231 <= nums[i] <= 231 - 1

Approach: Merge Sort with Two-Pointer Counting (Divide and Conquer)

Algorithm

1. Recursively split the array into halves until each subarray has one element
2. During each merge, count reverse pairs across the two halves: for every i in the left half, count how many j in the right half satisfy nums[i] > 2 * nums[j]
3. Because the right half is sorted, a single moving pointer j finds that count for all i in linear time
4. Merge the two sorted halves back together so the counting step remains valid at every level
5. Accumulate the cross-half counts from all merge levels into the final answer

Time & Space Complexity

• Time Complexity: O(n log n) - merge sort plus O(n) counting per merge level
• Space Complexity: O(n) - the temporary array used during merging

Java Implementation

public class ReversePairs {

    private int count;

    public int reversePairs(int[] nums) {
        count = 0;
        mergeSort(nums, new int[nums.length], 0, nums.length - 1);
        return count;
    }

    private void mergeSort(int[] nums, int[] temp, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        mergeSort(nums, temp, lo, mid);
        mergeSort(nums, temp, mid + 1, hi);

        int j = mid + 1;
        for (int i = lo; i <= mid; i++) {
            while (j <= hi && (long) nums[i] > 2L * nums[j]) {
                j++;
            }
            count += j - (mid + 1);
        }

        int p = lo;
        int q = mid + 1;
        int k = lo;
        while (p <= mid && q <= hi) {
            if (nums[p] <= nums[q]) {
                temp[k++] = nums[p++];
            } else {
                temp[k++] = nums[q++];
            }
        }
        while (p <= mid) {
            temp[k++] = nums[p++];
        }
        while (q <= hi) {
            temp[k++] = nums[q++];
        }
        System.arraycopy(temp, lo, nums, lo, hi - lo + 1);
    }

    // Test method
    public static void main(String[] args) {
        ReversePairs solver = new ReversePairs();
        int[] nums1 = {1, 3, 2, 3, 1};
        System.out.println("reversePairs([1,3,2,3,1]): " + solver.reversePairs(nums1)); // Expected: 2

        int[] nums2 = {2, 4, 3, 5, 1};
        System.out.println("reversePairs([2,4,3,5,1]): " + solver.reversePairs(nums2)); // Expected: 3
    }
}

Example Walkthrough

For nums = [1, 3, 2, 3, 1]:

1. Split into [1, 3] and [2, 3, 1]; after merging halves the subarrays become sorted, e.g. [1, 2, 3] and [1, 3]
2. Counting at the top-level merge: left = [1, 2, 3], right = [1, 3]
3. nums[1] = 3 > 2 * 1 and nums[3] = 3 > 2 * 1: exactly 2 reverse pairs (1, 4) and (3, 4)
4. No other left value exceeds twice a right value
5. Final answer: 2

Key Points

1. Comparison is Not Ordering: The reverse-pair test nums[i] > 2 * nums[j] is unrelated to the merge ordering, so counting is separate from merging
2. Long Casting: 2 * nums[j] can overflow int since nums[i] may be as large as 2^31 - 1, so cast to long
3. Monotone Pointer: The right half being sorted lets one pointer count valid pairs for every left element, keeping each merge at O(n)
4. No Double Counting: Each pair (i, j) is counted exactly once, at the merge level where i and j first fall into different halves
5. O(n log n): The divide and conquer approach beats the O(n²) brute force