Reverse Pairs

Problem

LeetCode 493 — Reverse Pairs

Given an array nums, return the number of reverse pairs: indices i < j where nums[i] > 2 * nums[j].

This is the same merge-sort inversion-count family as the classic interview question: “Count pairs where i < j and nums[i] > nums[j]” — with a stricter comparison (nums[i] > 2 * nums[j]).

Example

nums = [1, 3, 2, 3, 1]  →  2

Pairs: (3, 1) at indices (1, 4) and (3, 1) at indices (3, 4)
       nums[1]=3 > 2*1,  nums[3]=3 > 2*1

Classic inversion count on [2, 4, 1, 3, 5] → 3 pairs: (2,1), (4,1), (4,3).

Approach — Merge Sort + Count During Merge

Brute force: check all pairs (i, j) → O(n²).

Optimal: merge sort. While merging left and right halves (both sorted), count cross-half pairs in O(n) per level → O(n log n) total.

Two counting steps in one merge pass:

1. Before comparing heads: for each i in left, advance j in right while nums[i] > 2 * nums[j] — each such j forms a valid pair with this i (and all larger left elements too; handle via a dedicated pre-scan or inline count).
2. Standard merge: merge the two sorted halves into a temp buffer (same as merge sort).

The canonical inversion count uses step 2 only: when taking from right, add mid - i + 1 to the count (all remaining left elements form inversions with that right element).

Merge invariant (inversion count — interview core)

if nums[i] <= nums[j]  → take from left, i++
else                   → count += (mid - i + 1), take from right, j++

Reverse Pairs adds a second pass before merge: for each i in left, count j in right where nums[i] > 2 * nums[j] while both halves are sorted.

Complexity

• Time: O(n log n)
• Space: O(n) — merge temp array

Solution

class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }

    private int mergeSort(int[] nums, int l, int r) {
        if (l >= r) return 0;
        int mid = l + (r - l) / 2;
        int count = mergeSort(nums, l, mid) + mergeSort(nums, mid + 1, r);

        // count cross-half reverse pairs before merge
        int j = mid + 1;
        for (int i = l; i <= mid; i++) {
            while (j <= r && (long) nums[i] > 2L * nums[j]) j++;
            count += j - (mid + 1);
        }

        merge(nums, l, mid, r);
        return count;
    }

    private void merge(int[] nums, int l, int mid, int r) {
        int[] temp = new int[r - l + 1];
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r)
            temp[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
        while (i <= mid) temp[k++] = nums[i++];
        while (j <= r)     temp[k++] = nums[j++];
        System.arraycopy(temp, 0, nums, l, temp.length);
    }
}

Use long for 2 * nums[j] — overflow on large values.

Classic inversion count (same merge, simpler ask)

private int mergeSort(int[] nums, int l, int r) {
    if (l >= r) return 0;
    int mid = l + (r - l) / 2;
    int count = mergeSort(nums, l, mid) + mergeSort(nums, mid + 1, r);

    int[] temp = new int[r - l + 1];
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            count += mid - i + 1;
            temp[k++] = nums[j++];
        }
    }
    while (i <= mid) temp[k++] = nums[i++];
    while (j <= r)     temp[k++] = nums[j++];
    System.arraycopy(temp, 0, nums, l, temp.length);
    return count;
}

Why It Teaches You Something

One merge-sort skeleton covers a whole interview family — often asked as “Can you improve on O(n²)?” after merge sort implementation.

If you know the inversion merge invariant, LC 315 and LC 493 are variations — not new algorithms.