Reverse Pairs

The problem. Given an integer array nums, return the number of reverse pairs: index pairs i < j with nums[i] > 2 · nums[j].

Counting across two sorted halves, 1, 2, 3 and 1, 3. For the left value 3, the right values smaller than 3 divided by 2 — just 1 — count: one pair. For 1 and 2 nothing counts. Because both halves are sorted, the pointer into the right half only moves forward as the left value grows.

Example

nums = [1, 3, 2, 3, 1]  ->  2   (3 > 2·1 at indexes 1,4 and 3,4)
nums = [2, 4, 3, 5, 1]  ->  3   (4, 3 and 5 are each more than 2·1)

The idea: count across sorted halves with two pointers

It's Count Inversions with a different condition. Split in half; pairs inside each half are counted recursively; pairs across the halves are counted while both halves are sorted. But the condition a[i] > 2 · a[j] doesn't match the merge's own comparison, so do a separate counting pass first: for each left value a[i] in increasing order, move j forward through the right half while a[i] > 2 · a[j]. Since a[i] only grows, j never moves back — the whole pass is linear. Then merge as usual.

1. Brute force: check every pair

1function reversePairs(nums) {2  let count = 0;3  for (let i = 0; i < nums.length; i++) {4    for (let j = i + 1; j < nums.length; j++) {5      if (nums[i] > 2 * nums[j]) count++;6    }7  }8  return count;9}

JavaScript9 lines

Time O(n²), space O(1). Too slow for 5 × 10⁴ values.

2. Merge sort with a counting pass

Dry-run simulator

Reverse pairs (merge sort with a counting pass)

Before each merge, two pointers count the pairs across the sorted halves in one sweep.

1function reversePairs(nums) {2  const a = [...nums];3  const sortCount = (lo, hi) => {                 // sorts a[lo..hi), returns the reverse pairs inside it4    if (hi - lo <= 1) return 0;5    const mid = (lo + hi) >> 1;6    let count = sortCount(lo, mid) + sortCount(mid, hi);7    let j = mid;8    for (let i = lo; i < mid; i++) {              // both halves are sorted: j only moves forward9      while (j < hi && a[i] > 2 * a[j]) j++;10      count += j - mid;                           // a[mid..j) are all small enough for a[i]11    }12    const merged = [];13    let p = lo, q = mid;14    while (p < mid && q < hi) merged.push(a[p] <= a[q] ? a[p++] : a[q++]);15    while (p < mid) merged.push(a[p++]);16    while (q < hi) merged.push(a[q++]);17    for (let k = 0; k < merged.length; k++) a[lo + k] = merged[k];18    return count;19  };20  return sortCount(0, a.length);21}

JavaScript21 lines

Time O(n log n), space O(n). Each level does one linear counting pass and one linear merge. In Java and C++, compute 2 * a[j] in 64 bits — with values up to 2³¹ − 1 it overflows an int.

Comparing the approaches

Every pair: O(n²) time, O(1) space. Merge sort + counting pass: O(n log n) time, O(n) space.

A Fenwick tree (binary indexed tree) over the compressed values solves it in O(n log n) too — useful when the condition can't be counted with two pointers.

Edge cases to test

Negative numbers — [-5, -5]: -5 > 2 · (-5) = -10, so that's 1 pair.
Overflow — [2147483647, 2147483647]: 2 · 2147483647 overflows a 32-bit int.
Equal values — [1, 1]: 1 > 2 is false, 0 pairs.
Counting inside the merge loop — the merge's comparison is a[p] <= a[q], not the pair condition; keep the passes separate.

Variations

Count Inversions — the condition a[i] > a[j] fits inside the merge itself. Previous lesson.
Count of Range Sum — merge sort on prefix sums, counting pairs whose difference falls in a range.
Count of Smaller Numbers After Self — per-index counts through the same merge.

Was this helpful?