Reverse Pairs: Merge Sort for Counting Inversions

493. Reverse Pairs gives you an integer array nums and asks you to count the number of reverse pairs. A reverse pair is a pair (i, j) where i < j and nums[i] > 2 * nums[j].

For nums = [1, 3, 2, 3, 1], the answer is 2. The pair (1, 4) works because nums[1] = 3 > 2 * nums[4] = 2. The pair (3, 4) also works because nums[3] = 3 > 2 * nums[4] = 2. No other pairs satisfy the condition.

Why brute force is not enough

The obvious approach checks every pair (i, j) where i < j. That is O(n^2), which will time out when n reaches 50,000. You need something faster.

The trick is recognizing that this is a modified inversion counting problem. Classic inversion counting asks "how many pairs have nums[i] > nums[j]?" and merge sort solves it in O(n log n). This problem changes the condition to nums[i] > 2 * nums[j], but the same divide-and-conquer framework applies.

The key insight

During merge sort, after you recursively sort the left and right halves, both halves are in sorted order. You can count cross-half reverse pairs efficiently using two pointers before you merge.

Here is why sorted order helps. You want to count pairs where a left-half element L satisfies L > 2 * R for some right-half element R. Since the right half is sorted, once you find that L > 2 * R[j], you know L > 2 * R[k] for all k < j too. So you just move a pointer forward through the right half, and each left-half element picks up where the last one left off. The total work for the counting step across one merge is O(n), not O(n^2).

The total count is: reverse pairs in the left half + reverse pairs in the right half + cross-half reverse pairs. The recursion handles the first two. The two-pointer scan handles the third.

The solution

def reversePairs(nums):
    if len(nums) <= 1:
        return 0

    mid = len(nums) // 2
    left = nums[:mid]
    right = nums[mid:]

    count = reversePairs(left) + reversePairs(right)

    j = 0
    for i in range(len(left)):
        while j < len(right) and left[i] > 2 * right[j]:
            j += 1
        count += j

    nums[:] = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            nums.append(left[i])
            i += 1
        else:
            nums.append(right[j])
            j += 1
    nums.extend(left[i:])
    nums.extend(right[j:])

    return count

The function modifies nums in place to keep it sorted after each recursive call. That is essential - the counting step at each level depends on both halves being sorted from the recursion below.

Notice that the counting loop and the merging loop are separate. You count first using the > 2 * condition, then merge using the standard <= comparison. Keeping them separate avoids mixing up the two different comparisons.

The j pointer in the counting loop never resets between iterations of the outer for loop. Since left is sorted, if left[i] pushed j to some position, left[i+1] (which is >= left[i]) will only push j further. This is what makes the counting step O(n) total rather than O(n^2).

The walkthrough above uses a small array to show each phase clearly. On larger inputs the recursion goes deeper, but the same pattern repeats at every level: split, recurse, count cross-half pairs, merge.

Complexity analysis

The merge sort has log n levels of recursion. At each level, the total work across all merge operations is O(n) for both counting and merging. That gives O(n log n) overall. The O(n) space comes from the temporary arrays created during splitting and merging.

The building blocks

Merge sort for counting inversions. The core pattern here is using divide-and-conquer to count relationships between elements. Standard inversion counting checks nums[i] > nums[j]. This problem modifies the condition to nums[i] > 2 * nums[j], but the framework is identical. Once you understand how merge sort counts inversions, you can adapt it to any pairwise condition that respects sorted order.

Two-pointer technique on sorted arrays. The cross-half counting step relies on both halves being sorted. The pointer j advances monotonically because as you move to larger elements in the left half, the threshold 2 * right[j] only needs to grow. This amortized O(n) scan is what makes the approach efficient.

Divide and conquer with aggregation. The total count is the sum of counts from the left subproblem, the right subproblem, and the cross-boundary pairs. This additive decomposition is what lets you solve each piece independently and combine the results.

Edge cases to watch for

• All identical elements. If every element is the same, nums[i] > 2 * nums[j] is never true (since x is never > 2x for positive or zero values). The answer is 0. Your counting loop correctly finds nothing.
• Array of length 0 or 1. No pairs exist, so return 0. The base case handles this.
• Large negative numbers. When nums[j] is negative, 2 * nums[j] is more negative, making the condition easier to satisfy. The algorithm handles this naturally since it just compares values.
• Integer overflow with 2 * nums[j]. In languages with fixed-width integers, 2 * nums[j] can overflow. In Python this is not an issue, but in C++ or Java you should cast to long before multiplying.
• Already sorted arrays. Whether ascending or descending, the algorithm still works in O(n log n). A descending array like [5, 4, 3, 2, 1] produces many reverse pairs, while an ascending one produces none.

From understanding to recall

The algorithm has three distinct phases at each recursion level: recurse on halves, count cross-half pairs, merge. The part that usually trips people up in interviews is the counting loop. You need to remember two things.

First, the counting loop is separate from the merge loop. They use different comparisons (> 2 * for counting, <= for merging) and you must not combine them.

Second, the j pointer does not reset between iterations of the outer loop. This is what gives you O(n) counting instead of O(n^2). If you accidentally reset j to 0 each time, you get the right answer but with worse performance.

Spaced repetition helps lock in these details. Write the solution from scratch a few days later, and specifically check that you kept the counting and merging loops separate and that j does not reset. After a few sessions, the structure becomes automatic.

Related posts

• Sort List - Merge sort applied to linked lists, the same divide-and-conquer pattern in a different data structure
• Count of Smaller Numbers After Self - Another hard inversion-counting problem, solved with a Binary Indexed Tree
• Merge Sorted Array - The merge step in isolation, useful for building intuition about how two sorted sequences combine