Reverse Pairs

Hard
1087.

Reverse Pairs

Reverse Pairs is a hard coding problem on arrays, binary search and divide and conquer, asked in Amazon, Google, Meta and Intuit interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Reverse Pairs — Solution in Python, Java & C++

Reverse Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.

Reverse Pairs is a hard coding problem on arrays, binary search and divide and conquer, asked in Amazon, Google, Meta and Intuit interviews.

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

Hints for Reverse Pairs

  1. Hint 1

    The quadratic scan is too slow — the pairs have to be counted during a divide and conquer.

  2. Hint 2

    Inside a merge sort, count the pairs whose left index is in the left half and right index in the right half.

  3. Hint 3

    Because both halves are already sorted, that count is a single forward sweep before the merge.

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

  1. Recurse on [lo, mid) and [mid, hi), summing their counts.
  2. Sweep i across the left half, advancing j in the right half while work[i] > 2 · work[j]; add j - mid for each i.
  3. 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))

Java

public static int reversePairs(int[] nums) {
    int[] work = nums.clone();
    int[] buffer = new int[work.length];
    return rpSortCount(work, buffer, 0, work.length);
}

private static int rpSortCount(int[] work, int[] buffer, int lo, int hi) {
    if (hi - lo <= 1) return 0;
    int mid = (lo + hi) >>> 1;
    int total = rpSortCount(work, buffer, lo, mid) + rpSortCount(work, buffer, mid, hi);
    int j = mid;
    for (int i = lo; i < mid; i++) {
        while (j < hi && (long) work[i] > 2L * work[j]) j++;
        total += j - mid;
    }
    int 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 (int i = lo; i < hi; i++) work[i] = buffer[i];
    return total;
}

C++

static int rpSortCount(vector<int>& work, vector<int>& buffer, int lo, int hi) {
    if (hi - lo <= 1) return 0;
    int mid = (lo + hi) / 2;
    int total = rpSortCount(work, buffer, lo, mid) + rpSortCount(work, buffer, mid, hi);
    int j = mid;
    for (int i = lo; i < mid; i++) {
        while (j < hi && (long long) work[i] > 2LL * work[j]) j++;
        total += j - mid;
    }
    int 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 (int i = lo; i < hi; i++) work[i] = buffer[i];
    return total;
}

int reversePairs(vector<int>& nums) {
    vector<int> work = nums;
    vector<int> buffer(work.size(), 0);
    return rpSortCount(work, buffer, 0, (int) work.size());
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search