Reverse Pairs

HardDivide & Conquer · Merge Sort🧩 Recursion & Divide and Conquer LeetCode #493 ↗Updated Oct 30, 2026

Problem

Given an integer array nums, count the index pairs (i, j) with i < j where the earlier element is more than twice the later one, i.e. nums[i] > 2 · nums[j]. Values span the full int range, so the doubled value must not overflow.

Input[1,3,2,3,1]Output2 (3 > 2·1 twice)

Input[5,4,3,2,1]Output4

Input[-5,-5]Output1 (-5 > -10)

1 ≤ n ≤ 5·10⁴ · -2³¹ ≤ nums[i] ≤ 2³¹-1

Try it yourself

Java

class Solution {
    public int reversePairs(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

During merge sort, the left and right halves are each sorted and every left index is still before every right index. So the pairs that cross the midpoint can be counted with one forward-only pointer before merging — O(n) per level.

PatternRecursion & Divide and Conquer

Instinct If the answer for n items can be built from the same problem on halves (or smaller pieces) plus a cheap combine step - split, recurse, merge.

Memory hack Split it, trust it, stitch it - nail the base case, take the leap of faith on smaller calls, then glue their answers together.

Open the Recursion & Divide and Conquer guide →

Approaches

Brute ForceCheck Every Pair

Time O(n²)Space O(1)

Two nested loops test nums[i] > 2L * nums[j] for every i < j. Doing the doubling in long keeps values like 2³¹-1 from wrapping negative.

Java

public int reversePairs(int[] nums) {
    int count = 0;
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] > 2L * nums[j]) count++; // 2L: no int overflow
        }
    }
    return count;
}

Obviously correct; ~1.25·10⁹ checks at n = 5·10⁴ is too slow.

BetterFenwick Tree over Ranked Values

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

Scan left to right, keeping a Fenwick tree (BIT) of how many earlier values fall at each rank in the sorted array. For nums[j], binary-search how many earlier values are ≤ 2·nums[j]; the rest of the j earlier values form reverse pairs. Then insert nums[j].

Java

public int reversePairs(int[] nums) {
    int n = nums.length;
    long[] sorted = new long[n];
    for (int i = 0; i < n; i++) sorted[i] = nums[i];
    Arrays.sort(sorted);
    int[] bit = new int[n + 1];
    int count = 0;
    for (int j = 0; j < n; j++) {
        // earlier values <= 2*nums[j] are those with rank <= upperBound(2*nums[j])
        int notGreater = query(bit, upperBound(sorted, 2L * nums[j]));
        count += j - notGreater;
        update(bit, lowerBound(sorted, nums[j]) + 1); // 1-based rank
    }
    return count;
}
private int upperBound(long[] a, long target) { // first index with a[i] > target
    int lo = 0, hi = a.length;
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (a[mid] <= target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}
private int lowerBound(long[] a, long target) { // first index with a[i] >= target
    int lo = 0, hi = a.length;
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}
private void update(int[] bit, int i) {
    for (; i < bit.length; i += i & -i) bit[i]++;
}
private int query(int[] bit, int i) {
    int sum = 0;
    for (; i > 0; i -= i & -i) sum += bit[i];
    return sum;
}

Fast, but needs a sorted copy, rank lookups and a BIT — more moving parts.

OptimalMerge Sort with Cross-Count

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

Sort each half recursively (counting pairs inside it), then count pairs that straddle the midpoint: for each left value in increasing order, advance j through the right half while a[i] > 2·a[j]. Since left values only grow, j never moves back. Finally merge as usual so the parent sees a sorted range.

Java

public int reversePairs(int[] nums) {
    return sortCount(nums, 0, nums.length - 1, new int[nums.length]);
}
private int sortCount(int[] a, int lo, int hi, int[] tmp) {
    if (lo >= hi) return 0;
    int mid = (lo + hi) >>> 1;
    int count = sortCount(a, lo, mid, tmp) + sortCount(a, mid + 1, hi, tmp);
    // both halves sorted: count cross pairs with a forward-only pointer
    int j = mid + 1;
    for (int i = lo; i <= mid; i++) {
        while (j <= hi && a[i] > 2L * a[j]) j++;
        count += j - (mid + 1);
    }
    // standard merge into tmp, then copy back
    int p = lo, q = mid + 1, k = lo;
    while (p <= mid && q <= hi) tmp[k++] = (a[p] <= a[q]) ? a[p++] : a[q++];
    while (p <= mid) tmp[k++] = a[p++];
    while (q <= hi) tmp[k++] = a[q++];
    System.arraycopy(tmp, lo, a, lo, hi - lo + 1);
    return count;
}

Dry run[1,3,2,3,1]

i left ptrj right ptr changed

halves
1

2

3

·

1

3

left [1,2,3] | right [1,3]
i=1
1
i
2

3

·

1
j
3

1 > 2? no → +0
i=2
1

2
i
3

·

1
j
3

2 > 2? no → +0
i=3
1

2

3
i
·

1

3
j
3 > 2 → j++, +1
merge
1

1

2

3

3

cross pairs = 1

Self-contained O(n log n) with a linear two-pointer pass per level — the classic answer.

Pro tip

Keep the counting loop separate from the merge loop — the two use different comparisons (> 2x vs ≤).

At a glance

Level	Approach	Time	Space
Brute Force	Check Every Pair	`O(n²)`	`O(1)`
Better	Fenwick Tree over Ranked Values	`O(n log n)`	`O(n)`
Optimal	Merge Sort with Cross-Count	`O(n log n)`	`O(n)`

Common pitfalls

Computing 2 * nums[j] in int — overflows for |values| > 2³⁰.
Counting inside the merge comparison — the merge order and the 2x condition disagree.
Resetting j for every i — turns the cross-count back into O(n²).

Interview tips

Link it to “count inversions”: same merge-sort skeleton, different cross condition.
Explain why left-before-right is preserved when both halves are sorted independently.
Mention the BIT alternative as a follow-up if the interviewer wants an online version.

Pattern

Merge sort with cross-half counting → count pairs i < j satisfying a monotone comparison between their values.

My notes saved in this browser