Reverse Pairs — Merge Sort vs Fenwick Tree (BIT) Solutions Explained

Problem Statement#

LeetCode 493 — Reverse Pairs | Difficulty: Hard

Given an integer array nums, return the number of reverse pairs in the array. A reverse pair is a pair (i, j) where:

• 0 is less than or equal to i is less than j is less than nums.length
• nums[i] is greater than 2 * nums[j]

Constraints:

• 1 is less than or equal to nums.length, which is less than or equal to 5 * 10^4
• -2^31 is less than or equal to nums[i], which is less than or equal to 2^31 minus 1

Example 1:

Input:  nums = [1, 3, 2, 3, 1]
Output: 2
Explanation:
  Pair (1, 4): nums[1]=3, 2*nums[4]=2 -> 3 > 2  yes
  Pair (3, 4): nums[3]=3, 2*nums[4]=2 -> 3 > 2  yes

Example 2:

Input:  nums = [2, 4, 3, 5, 1]
Output: 3
Explanation:
  Pair (1, 4): 4 > 2*1 = 2  yes
  Pair (2, 4): 3 > 2*1 = 2  yes
  Pair (3, 4): 5 > 2*1 = 2  yes

Why This Problem Matters#

Reverse Pairs is the gold-standard interview test for divide-and-conquer counting and the Fenwick Tree on a doubled value space. Google, Meta, and Amazon all use it as a senior-level signal because the brute-force O(n^2) is trivially obvious, but pushing to O(n log n) requires you to either modify merge sort or apply a BIT with careful coordinate compression on a transformed value set.

Beyond the interview, this exact pattern shows up in computational finance (counting price-doubling events), genomic alignment scoring, and database query optimizers that count cross-shard inversions. Understanding both the merge-sort and the BIT solution unlocks the entire family of "count pairs satisfying a property across an index split" problems.

The Core Insight#

There are two canonical O(n log n) approaches. Both rely on the same key observation: for any index j, the elements nums[i] with i less than j and nums[i] greater than 2 * nums[j] can be counted in O(log n) if we maintain a sorted structure over the seen-so-far values.

Approach A — Modified Merge Sort#

Standard merge sort already sorts halves recursively. We piggyback the counting on the merge step.

Key invariant: when merging two sorted halves left and right, every pair (i, j) with i in left and j in right satisfies i less than j. So we just need to count, for each i in left, how many j in right satisfy left[i] greater than 2 * right[j].

Because left and right are sorted, a two-pointer sweep does this in O(n) per merge level. Total: O(n log n).

Approach B — Fenwick Tree on Doubled Coordinates#

For each j, count seen-so-far elements that are strictly greater than 2 * nums[j]. Compress the union of nums and 2 * nums + 1 into ranks. Sweep left to right, query the BIT for the count of ranks above rank(2 * nums[j]), then insert nums[j].

Both run in O(n log n). Merge sort has cleaner code and slightly better constants; the BIT generalizes more easily to range-count variants.

The subtle pitfall in both approaches is integer overflow: 2 * nums[j] can exceed 2^31 when nums[j] is near INT_MAX or INT_MIN. Use 64-bit arithmetic (long long in C++, BigInt or careful sign handling in JS).

Visual Dry Run#

Trace nums = [2, 4, 3, 5, 1] with merge sort.

Initial:        [2, 4, 3, 5, 1]
Split:          [2, 4]  |  [3, 5, 1]
Recurse left:   sort -> [2, 4], no pairs counted (each leaf alone)
Recurse right:  [3]  |  [5, 1]  ->  [3]  |  sort([5,1]) = [1,5]
                count pairs across [3] and [1,5]:
                  3 > 2*1? yes -> count += 1
                  3 > 2*5? no
                merge -> [1, 3, 5], total so far: 1
Top level merge of [2,4] and [1,3,5]:
  for left=2: 2 > 2*1=2? no   -> 0
  for left=4: 4 > 2*1=2? yes  -> j=1
              4 > 2*3=6? no   -> stop, count += 1
  total so far: 2
Final merge gives [1, 2, 3, 4, 5], answer = 1 + 2 = 3

The two-pointer step in each merge runs in O(n) because both pointers only advance forward — never reset.

Solution (Optimal)#

Python — Modified Merge Sort#

from typing import List
 
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        # merge sort that counts pairs (i, j) where left[i] > 2 * right[j]
        def merge_sort(arr: List[int]) -> int:
            if len(arr) <= 1:
                return 0                              # base case: no pairs possible
            mid = len(arr) // 2
            left, right = arr[:mid], arr[mid:]
            count = merge_sort(left) + merge_sort(right)  # recurse, both halves now sorted
 
            # count cross pairs using two pointers (both halves sorted)
            j = 0
            for x in left:                            # left is sorted ascending
                while j < len(right) and x > 2 * right[j]:
                    j += 1                            # advance while condition holds
                count += j                            # j is the number of valid right elements
 
            # merge step: standard two-pointer sorted merge in-place
            i = j2 = k = 0
            while i < len(left) and j2 < len(right):
                if left[i] <= right[j2]:
                    arr[k] = left[i]; i += 1
                else:
                    arr[k] = right[j2]; j2 += 1
                k += 1
            while i < len(left):
                arr[k] = left[i]; i += 1; k += 1
            while j2 < len(right):
                arr[k] = right[j2]; j2 += 1; k += 1
            return count
 
        return merge_sort(nums[:])                    # work on a copy to keep input intact

Python — Fenwick Tree (Alternative)#

from typing import List
 
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        # build coordinate set from both nums and 2*nums (for the comparison threshold)
        coords = sorted(set(nums) | {2 * x for x in nums})
        rank = {v: i + 1 for i, v in enumerate(coords)}    # 1-indexed
        size = len(coords)
        bit = [0] * (size + 1)
 
        def update(i: int) -> None:
            while i <= size:
                bit[i] += 1
                i += i & (-i)
 
        def query(i: int) -> int:
            s = 0
            while i > 0:
                s += bit[i]
                i -= i & (-i)
            return s
 
        ans = 0
        # sweep left to right; for each j, count seen i with nums[i] > 2 * nums[j]
        for x in nums:
            r = rank[2 * x]                            # rank of threshold
            ans += query(size) - query(r)              # count of seen ranks strictly above r
            update(rank[x])                            # insert this nums[j]
        return ans

JavaScript — Modified Merge Sort#

var reversePairs = function(nums) {
    const mergeSort = (arr) => {
        if (arr.length <= 1) return 0;
        const mid = arr.length >> 1;
        const left = arr.slice(0, mid);
        const right = arr.slice(mid);
        let count = mergeSort(left) + mergeSort(right);  // both halves sorted after this
 
        // two-pointer count: for each x in left, count rights with x > 2*right[j]
        let j = 0;
        for (const x of left) {
            while (j < right.length && x > 2 * right[j]) j++;
            count += j;                                  // j elements of right satisfy condition
        }
 
        // standard merge
        let i = 0, j2 = 0, k = 0;
        while (i < left.length && j2 < right.length) {
            arr[k++] = left[i] <= right[j2] ? left[i++] : right[j2++];
        }
        while (i < left.length) arr[k++] = left[i++];
        while (j2 < right.length) arr[k++] = right[j2++];
        return count;
    };
 
    return mergeSort([...nums]);                         // copy to preserve input
};

Complexity: Time O(n log n) — log n merge levels times O(n) merge plus counting. Space O(n) for the temporary arrays during recursion.

Common Mistakes#

1. Counting after the merge instead of before. Once you merge the two halves, the index split is gone — you cannot tell which elements came from the left versus the right. Count first, merge second.
2. Resetting the right pointer for each left element. That ruins the linear two-pointer guarantee and turns the count step into O(n^2). The pointer is monotonic across the entire left sweep.
3. Using > right[j] * 2 and overflowing. When right[j] equals 2^31 minus 1, doubling overflows. In Java or C++ use long; in JavaScript use a safe comparison or BigInt.
4. Forgetting to compress 2 * nums. In the BIT solution, the threshold 2 * nums[j] may not appear in the original nums. The coordinate set must include both nums and the doubled values.
5. Counting non-strict pairs. The condition is strictly greater than, not greater than or equal to. The two-pointer condition is x > 2 * right[j], not >=.
6. Re-sorting both halves at the top of merge. That makes it O(n^2 log n). The merge step itself does the sorting linearly.

Interview Tips#

• Mention both solutions, pick merge sort for cleanliness. Saying "merge sort gives the cleanest counting; BIT works if you also need range frequency queries" is exactly the trade-off senior interviewers want to hear.
• Address overflow proactively. Even before you start coding, say "I will use 64-bit arithmetic for the threshold". This earns trust without prompting.
• Walk the two-pointer invariant. Many candidates write merge sort but cannot explain why the inner pointer never resets. Demonstrating that linear-merge intuition is the key signal.
• Connect to inversion counting. Reverse Pairs is a small variation of "count inversions in an array". Mentioning this connection shows you see the family pattern.
• Test edge cases out loud: empty array, single element, all equal values, all decreasing, very large negatives.

Follow-up Questions#

1. Count pairs with nums[i] greater than k * nums[j] for arbitrary k. Same template, parameterize the multiplier and respect overflow.
2. Count Smaller Numbers After Self (LeetCode 315). Strictly smaller version — fewer overflow concerns, identical scaffold.
3. Count of Range Sum (LeetCode 327). Apply merge sort to prefix sums; count pairs whose difference falls in a target window.
4. Streaming version where elements arrive one at a time. Use a Fenwick Tree or an Order-Statistics Tree, since merge sort needs the full array up front.
5. 2D variant: count of points dominated by another point. Sort by x, sweep, use a BIT on compressed y.
6. Parallelize on huge data. Map-reduce: each shard counts internal pairs and exposes its sorted sequence; reducers count cross-shard pairs by merging.

Key Takeaways#

• Modified merge sort counts cross-pairs during the merge step using a two-pointer sweep that runs in O(n) per level for O(n log n) total — the gold-standard pattern for "count pairs across an index split".
• Always count before merging, otherwise the index ordering that defines the pair is gone.
• The two-pointer monotonic advance is the secret to linear merge counting. If your right pointer ever resets, your complexity has degraded.
• The Fenwick Tree alternative requires compressing both nums and 2 * nums into the coordinate set so the threshold rank is queryable.
• Watch for integer overflow on 2 * nums[j]. Use 64-bit arithmetic in any language with fixed-width integers.
• This template generalizes to inversion counting, Count of Range Sum, and any "count pairs satisfying a multiplicative or additive comparison" problem.