Reverse Pairs

Hard Arrays & Hashing Merge Sort Like Approach Original on LeetCode

Reverse Pairs is a hard arrays & hashing problem solved with the merge sort like approach pattern. The best approach, optimal (merge sort with a counting pass), runs in O(n log n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (check every pair) up.

Problem

Given an integer array nums, a pair of indices (i, j) is called a reverse pair when 0 <= i < j < nums.length and nums[i] > 2 * nums[j].

Return the number of reverse pairs in nums. Note that the doubled value can exceed the 32-bit integer range.

Examples

Example 1

Input
nums = [5, 1, 4, 2]
Output
2
Why
The pairs are (0, 1) since 5 > 2 * 1, and (0, 3) since 5 > 2 * 2. The pair (2, 3) fails because 4 is not greater than 4.

Example 2

Input
nums = [3, 6, 2, 0]
Output
4
Why
Valid pairs: (0, 3), (1, 2), (1, 3), (2, 3).

Example 3

Input
nums = [-4, -3]
Output
1
Why
-4 > 2 * (-3) = -6, so the single pair counts.

Constraints

  • 1 <= nums.length <= 5 * 10^4
  • -2^31 <= nums[i] <= 2^31 - 1

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (check every pair)O(n²)O(1)
Optimal (merge sort with a counting pass)O(n log n)O(n)

1Brute force (check every pair)

TimeO(n²)n(n - 1) / 2 pairs.
SpaceO(1)A counter and two indices.

Try every pair i < j and count those with nums[i] > 2 * nums[j], computing the double in 64-bit.

  1. Loop i from 0 to n - 1, and j from i + 1 to n - 1.
  2. If (long) nums[i] > 2L * nums[j], increment the count.
class Solution {
    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 ((long) nums[i] > 2L * nums[j]) count++;
        return count;
    }
}

2Optimal (merge sort with a counting pass)

TimeO(n log n)Each of the log n levels does a linear counting pass and a linear merge.
SpaceO(n)The merge buffer plus O(log n) recursion stack.

Every pair (i, j) with i < j has both ends in the same half of some merge-sort call, or i in the left half and j in the right half of exactly one call. Count the cross pairs right before merging: both halves are already sorted, so for each left element (in increasing order) a pointer into the right half only ever moves forward over elements with 2 * right < left. Then merge as usual.

  1. sort(lo, hi) returns the number of reverse pairs inside nums[lo..hi] and sorts that range.
  2. Recurse on both halves and add their counts.
  3. Set j = mid + 1. For each i in lo..mid: while j <= hi and nums[i] > 2L * nums[j], j++. Add j - (mid + 1).
  4. Merge the two sorted halves through a buffer.
class Solution {
    private int[] tmp;

    public int reversePairs(int[] nums) {
        tmp = new int[nums.length];
        return sort(nums, 0, nums.length - 1);
    }

    private int sort(int[] a, int lo, int hi) {
        if (lo >= hi) return 0;
        int mid = (lo + hi) >>> 1;
        int count = sort(a, lo, mid) + sort(a, mid + 1, hi);
        int j = mid + 1;
        for (int i = lo; i <= mid; i++) {
            while (j <= hi && (long) a[i] > 2L * a[j]) j++;
            count += j - (mid + 1);
        }
        int i = lo, k = lo;
        j = mid + 1;
        while (i <= mid && j <= hi) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
        while (i <= mid) tmp[k++] = a[i++];
        while (j <= hi) tmp[k++] = a[j++];
        for (k = lo; k <= hi; k++) a[k] = tmp[k];
        return count;
    }
}

Edge cases to test

  • Equality is not enough: nums[i] == 2 * nums[j] does not count
  • Negative numbers, where doubling makes a value smaller
  • Values near the int limits, where 2 * nums[j] overflows 32 bits
  • Single element (answer 0)

Hints

Hint 1

Checking every pair is O(n²). Can you count pairs between two halves faster if both halves are sorted?

Hint 2

During merge sort, before merging the two sorted halves, walk a pointer through the right half for each left element.

Hint 3

Because both halves are sorted, the right pointer only moves forward. Use 64-bit arithmetic for 2 * nums[j].

FAQ

What is the best time complexity for Reverse Pairs?

Optimal (merge sort with a counting pass) runs in O(n log n) time and O(n) extra space. Each of the log n levels does a linear counting pass and a linear merge.

Which pattern does Reverse Pairs use?

It is a arrays & hashing problem that uses the merge sort like approach pattern. Other problems with the same pattern: Count Inversions, Arranging the array, Sort an Array.

Is there a brute force solution for Reverse Pairs?

Yes. Brute force (check every pair) takes O(n²) time and O(1) space. Try every pair i < j and count those with nums[i] 2 nums[j], computing the double in 64-bit.

Which edge cases should I test for Reverse Pairs?

Equality is not enough: nums[i] == 2 nums[j] does not count; Negative numbers, where doubling makes a value smaller; Values near the int limits, where 2 nums[j] overflows 32 bits; Single element (answer 0).