Reverse Pairs — Hard Problem & Solution

A reverse pair is a pair of indices i 2 · nums[j]. Return the number of reverse pairs in nums.

Difficulty: Hard
Topics: Arrays, Binary Search, Divide and Conquer, Binary Indexed Tree, Merge Sort
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A reverse pair is a pair of indices i < j with nums[i] > 2 · nums[j].

Return the number of reverse pairs in nums.

Example 1

Input: nums = [1,3,2,3,1]
Output: 2
Explanation: `(1,4)` with 3 > 2 and `(3,4)` with 3 > 2.

Example 2

Input: nums = [2,4,3,5,1]
Output: 3
Explanation: `(1,4)`, `(2,4)` and `(3,4)`.

Example 3

Input: nums = [5,4,3,2,1]
Output: 4

Constraints

1 <= nums.length <= 5 * 10^4
-10^9 <= nums[i] <= 10^9

How to solve Reverse Pairs

Merge sort with a counting step. After both halves are sorted, count the cross pairs i in the left, j in the right with nums[i] > 2 · nums[j]; because both halves are sorted, a single pointer over the right half suffices. Then merge and return the total.

Approach

Recurse on [lo, mid) and [mid, hi), summing their counts.
Sweep i across the left half, advancing j in the right half while work[i] > 2 · work[j]; add j - mid for each i.
Merge the two halves back into sorted order.

Why it works

The counting sweep is linear rather than quadratic because both halves are sorted: as i moves right its value grows, so the threshold j only ever moves right too — it never backtracks. Counting before the merge is essential, since the merge destroys the separation between the halves that the pair definition relies on.

Complexity

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

Pitfalls

2 · nums[j] overflows a 32-bit integer at the upstream bounds — the comparison needs 64-bit arithmetic there.
The count must be taken before merging the halves.
The j pointer is shared across the whole sweep; resetting it per i makes the step quadratic again.

Reference solution

Python

from typing import List

def reversePairs(nums: List[int]) -> int:
    work = nums[:]

    def sort_count(lo: int, hi: int) -> int:
        if hi - lo <= 1:
            return 0
        mid = (lo + hi) // 2
        total = sort_count(lo, mid) + sort_count(mid, hi)
        j = mid
        for i in range(lo, mid):
            while j < hi and work[i] > 2 * work[j]:
                j += 1
            total += j - mid
        work[lo:hi] = sorted(work[lo:hi])
        return total

    return sort_count(0, len(work))

JavaScript

var reversePairs = function(nums) {
    var work = nums.slice();
    var buffer = [];
    for (var t = 0; t < work.length; t++) buffer.push(0);
    var sortCount = function(lo, hi) {
        if (hi - lo <= 1) return 0;
        var mid = (lo + hi) >> 1;
        var total = sortCount(lo, mid) + sortCount(mid, hi);
        var j = mid, i;
        for (i = lo; i < mid; i++) {
            while (j < hi && work[i] > 2 * work[j]) j++;
            total += j - mid;
        }
        var a = lo, b = mid, w = lo;
        while (a < mid || b < hi) {
            if (b >= hi || (a < mid && work[a] <= work[b])) buffer[w++] = work[a++];
            else buffer[w++] = work[b++];
        }
        for (i = lo; i < hi; i++) work[i] = buffer[i];
        return total;
    };
    return sortCount(0, work.length);
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue