Reverse Pairs Solution

Problem

Given an integer array, count how many "reverse pairs" exist — pairs of indices (i, j) where i < j and the left element is strictly greater than twice the right element.

Input: nums = [1, 3, 2, 3, 1]
Output: 2
Explanation: The pairs are (nums[1], nums[4]) = (3, 1) since 3 > 2×1, and (nums[3], nums[4]) = (3, 1) for the same reason.

A second example: nums = [2, 4, 3, 5, 1] → 3 pairs: (4,1), (3,1), (5,1).

Intuition

Checking every pair takes O(n²) time. The key insight for a faster solution is the same one that powers merge sort: once both halves of the array are sorted, you can sweep across them with two pointers to count all valid cross-partition pairs in O(n) rather than O(n²). Recurse on each half, count cross-half pairs, then merge — the total work per level is O(n), and there are O(log n) levels.

Approach 1 — Brute Force

Check every ordered pair (i, j) with i < j and increment a counter whenever the condition holds.

Iterate i from 0 to n - 2.
For each i, iterate j from i + 1 to n - 1.
If nums[i] > 2 * nums[j], increment the count.
Return the count.

1def reversePairs(self, nums: List[int]) -> int:
2    count = 0
3    for i in range(len(nums)):
4        for j in range(i + 1, len(nums)):
5            if nums[i] > 2 * nums[j]:
6                count += 1
7    return count

Time: O(n²) — every pair is examined once. Space: O(1) — only a counter variable.

Approach 2 — Merge Sort

Run merge sort on the array. Before each merge step, both halves are already sorted, so sweep through them with two pointers to count all cross-partition pairs in O(n); then complete the normal merge. Pairs within each half are handled by the recursive calls.

Base case: a subarray of length ≤ 1 has zero pairs.
Split the subarray at its midpoint and recurse on each half, accumulating their pair counts.
Count cross-partition pairs: use pointer j starting at mid. For each left-half element arr[i], advance j while arr[i] > 2 * arr[j]; add j - mid to the count. Because the left half is sorted, j never needs to go backwards as i advances.
Merge the two sorted halves into one sorted subarray using standard merge sort.
Return the accumulated count.

1def reversePairs(self, nums: List[int]) -> int:
2    def merge_count(arr: List[int], left: int, right: int) -> int:
3        if right - left <= 1:
4            return 0
5
6        mid = (left + right) // 2
7        count = merge_count(arr, left, mid) + merge_count(arr, mid, right)
8
9        # Count cross-partition pairs before merging (both halves are sorted here)
10        j = mid
11        for i in range(left, mid):
12            while j < right and arr[i] > 2 * arr[j]:
13                j += 1
14            count += j - mid  # all arr[mid..j-1] satisfy the condition for arr[i]
15
16        # Standard merge into a temporary buffer, then write back
17        merged = []
18        l, r = left, mid
19        while l < mid and r < right:
20            if arr[l] <= arr[r]:
21                merged.append(arr[l]); l += 1
22            else:
23                merged.append(arr[r]); r += 1
24        merged.extend(arr[l:mid])
25        merged.extend(arr[r:right])
26        arr[left:right] = merged
27
28        return count
29
30    return merge_count(nums, 0, len(nums))

Time: O(n log n) — the merge sort makes O(log n) levels, and each level does O(n) work for counting and merging. Space: O(n) — the temporary merge buffer at each level (O(n) total across any one level).

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(1)	Only acceptable for very small arrays (n < 1000)
Merge Sort	O(n log n)	O(n)	The standard approach for any realistic input

Common Mistakes

Merging before counting — the counting step relies on both halves being sorted; if you run the merge first, the subarray is fully sorted and cross-partition boundaries are gone, making counting impossible. Always count, then merge.
Using integer division instead of multiplication — writing nums[i] / 2 > nums[j] instead of nums[i] > 2 * nums[j] causes integer truncation: 3 / 2 = 1 in integer division, so 3 / 2 > 1 is false, but 3 > 2 * 1 is true. The condition must be checked by multiplying.
Integer overflow when doubling — 2 * nums[j] can overflow a 32-bit integer when nums[j] is large (up to 2³¹ − 1). Cast to long (2L * nums[j] in Java, 2LL * nums[j] in C++) before multiplying.
Counting j - left instead of j - mid — the count of right-half elements satisfying the condition for arr[i] is j - mid, not j - left. left is the start of the whole subarray, not the right half; using it inflates the count with left-half indices.
Resetting j to mid inside the i loop — j should never be reset between iterations of i. Because the left half is sorted ascending, if arr[i] > 2 * arr[j], then arr[i+1] >= arr[i] also satisfies it for everything up to j, so the pointer only ever moves forward.

Reverse Pairs — Solution