Topics › Arrays › Hard

Reverse Pairs

Hard TUF ID 26 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an integer array nums. A reverse pair is a pair of indices (i, j) with i < j and nums[i] > 2 * nums[j]. Return the number of reverse pairs.

Constraints: 0 ≤ n ≤ 5 × 10^4 (LeetCode) or up to 10^5 on other sheets, values fit in a 32-bit signed integer. 2 * nums[j] does not fit in an int for large values, and the count may exceed int, so use long for both.

Example 1

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

The pairs are (1, 4) with 3 > 2 × 1 and (3, 4) with 3 > 2 × 1. The pair (2, 4) fails because 2 > 2 × 1 is false.

Example 2

nums = [2, 4, 3, 5, 1]
answer = 3

4 > 2, 3 > 2 and 5 > 2, all with the final 1.

Approach 1: Brute force

Intuition. Check every pair with i < j against the condition. The only care needed is arithmetic: 2 * nums[j] must be computed in long.

Algorithm.

1. For every i, for every j > i: if nums[i] > 2 * nums[j] (in long), increment the count.
2. Return the count.

static long bruteForce(int[] nums) {
    long count = 0;
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if ((long) nums[i] > 2L * nums[j]) count++;
        }
    }
    return count;
}

Complexity. Time O(n^2). Space O(1).

For n = 5 × 10^4 this is 1.25 × 10^9 comparisons, too slow by a comfortable margin.

Approach 2: Optimal, merge sort with a separate counting pass

Intuition. This is a close cousin of Count Inversions. Split the array, count pairs inside each half recursively, and count cross pairs (i in the left half, j in the right half) while both halves are sorted. The difference is that the condition a[i] > 2 * a[j] is not the same as the merge comparison a[i] <= a[j], so the counting cannot be folded into the merge loop. Instead run a dedicated two-pointer pass before merging.

Both halves are sorted, so for a fixed left element a[i] the right elements satisfying a[i] > 2 * a[j] form a prefix a[mid+1 .. j-1] of the right half. As i increases, a[i] grows, so the prefix can only get longer; pointer j never moves backwards. The whole counting pass is therefore linear, and afterwards an ordinary merge keeps the invariant that each recursive call returns a sorted range.

Algorithm.

1. If the range has fewer than two elements, return 0.
2. Recurse on both halves and add their counts.
3. Counting pass: j = mid + 1. For each i in lo .. mid, advance j while j ≤ hi and a[i] > 2 * a[j]; then add j - (mid + 1).
4. Standard merge of the two sorted halves into tmp, copy back, return the count.

static long optimal(int[] nums) {
    int[] a = nums.clone();                                  // sorting happens on a copy
    return mergeSortCount(a, new int[a.length], 0, a.length - 1);
}

static long mergeSortCount(int[] a, int[] tmp, int lo, int hi) {
    if (lo >= hi) return 0;
    int mid = lo + (hi - lo) / 2;
    long count = mergeSortCount(a, tmp, lo, mid) + mergeSortCount(a, tmp, mid + 1, hi);
    int j = mid + 1;                                         // counting pass: both halves are sorted
    for (int i = lo; i <= mid; i++) {
        while (j <= hi && (long) a[i] > 2L * a[j]) j++;      // j only moves forward because a[i] grows
        count += j - (mid + 1);                              // a[mid+1 .. j-1] all satisfy a[i] > 2 * a[j]
    }
    int i = lo, k = lo;                                      // ordinary merge
    j = mid + 1;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi) tmp[k++] = a[j++];
    System.arraycopy(tmp, lo, a, lo, hi - lo + 1);
    return count;
}

Dry run on [1, 3, 2, 3, 1]. Split into [1, 3, 2] and [3, 1].

• [1, 3, 2] splits into [1, 3] (no pair: 1 > 6? no) and [2]. Cross count between sorted [1, 3] and [2]: 1 > 4? no; 3 > 4? no. Zero. Sorted [1, 2, 3].
• [3, 1]: 3 > 2, one pair. Sorted [1, 3].
• Top level, left [1, 2, 3], right [1, 3]:

Total 0 + 1 + 1 = 2.

Complexity. Time O(n log n): at each of the log n levels the counting pass and the merge are both linear. Space O(n) for the buffer plus O(log n) recursion.

Why not count inside the merge loop as in Count Inversions? There, the merge decision (a[i] <= a[j]) coincides with the pair condition, so each emitted right element knows exactly which left elements beat it. Here the merge compares a[i] with a[j] but the pair condition compares a[i] with 2 * a[j]; the two pointers would need to move at different moments. Keeping two separate linear passes is cleaner and costs nothing asymptotically.

Edge cases and pitfalls

• Overflow. 2 * Integer.MIN_VALUE and 2 * Integer.MAX_VALUE overflow int. Write 2L * a[j] and cast a[i] to long. The Java test [MAX, MAX, MIN, MIN] expects 5 pairs: four of the form MAX > 2 · MIN and one MIN > 2 · MIN (since -2^31 > -2^32), and an int version gets this wrong.
• Equal values. 2 > 2 × 2 is false, so [2, 2, 2, 2] has no reverse pairs. Also x > 2x is false for every x ≥ 0, so a pair needs either a strictly larger nums[i] or negative values.
• Negative numbers. -5 > 2 × (-3) = -6 is true, so negatives do form pairs even when they are smaller in absolute terms. The sorted-prefix argument still holds because doubling preserves order.
• Empty and single-element arrays. Return 0 immediately via lo >= hi.
• Large answers. The test with desc = 2n, 2n-2, ..., 2 for n = 10^5 has about 2.5 × 10^9 reverse pairs; keep the counter in long.
• Forgetting to reset j. The counting pass leaves j somewhere in the right half; the merge must start again from mid + 1.
• Mutating the input. The method sorts a clone so the caller’s array survives.

Related problems

• Count Inversions is the simpler condition nums[i] > nums[j], where counting happens inside the merge.
• Merge Sorting is the underlying algorithm.
• Merge two sorted arrays without extra space is another problem built on the merge step.