Reverse Pairs [Hard] — The Modified Merge Sort That Counts Before It Merges

Problem Statement#

Given an integer array nums, return the number of reverse pairs in the array.

A reverse pair is a pair (i, j) where 0 &lt;= i < j < nums.length and nums[i] > 2 * nums[j].

Example 1:

Input:  nums = [1, 3, 2, 3, 1]
Output: 2
Explanation: The pairs are (1,4) → nums[1]=3 > 2*nums[4]=2  ✓
                            (3,4) → nums[3]=3 > 2*nums[4]=2  ✓

Example 2:

Input:  nums = [2, 4, 3, 5, 1]
Output: 3
Explanation: The pairs are (1,4) → 4 > 2*1=2  ✓
                            (2,4) → 3 > 2*1=2  ✓
                            (3,4) → 5 > 2*1=2  ✓

Constraints:

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

Why This Problem Matters#

LeetCode 493 is a staple at Amazon and Google specifically because it separates candidates who can recognise when divide-and-conquer applies from those who just pattern-match merge sort. The problem looks like a simple inversion-count variant, but it contains a subtle ordering constraint that breaks almost every first attempt: you cannot count and merge in the same pass.

This problem sits at the intersection of two ideas that every senior engineer is expected to own:

1. Divide-and-conquer reasoning — trusting that once sub-problems are solved, combining their results only requires reasoning about cross-boundary interactions.
2. Two-pointer optimisation on sorted data — once two sub-arrays are sorted, a linear scan with monotone pointers is sufficient to count all qualifying pairs.

Beyond the coding challenge, this pattern is the foundation for the Binary Indexed Tree (BIT / Fenwick Tree) approach to order-statistic problems. If you deeply understand why the merge sort approach works, the BIT alternative becomes intuitive rather than mysterious.

Real interview signal: An interviewer at a FAANG company is not just checking whether you know merge sort. They are watching to see if you can articulate why two separate passes (count, then merge) are necessary. Candidates who conflate the two steps produce subtly wrong answers that pass some test cases and fail others — a red flag that is worse than not knowing the algorithm at all.

The Modified Merge Sort Insight#

Why Brute Force Fails#

The naive approach checks every pair (i, j) with i < j and tests whether nums[i] > 2 * nums[j]. That is O(n^2) time — for n = 50,000 that is 2.5 billion operations. It will time out.

Why Plain Merge Sort Fails Too#

You might think: during the merge step of standard merge sort, when I pick right[k] over left[i], all remaining elements in left[i..] form inversions with right[k]. Why not just adapt that?

The problem is the condition nums[i] > 2 * nums[j]. This is not the same as the standard inversion condition nums[i] > nums[j]. Specifically, the two conditions are not equivalent, so elements that satisfy one may not satisfy the other. If you try to count reverse pairs and merge in a single pass, the act of merging changes the relative positions of elements, making it impossible to correctly identify which pairs cross the boundary with the > 2 * condition.

The core insight: You need two separate passes over the two sorted halves — one pass to count qualifying cross-pairs, and a completely separate pass to merge. Mixing them corrupts both operations.

The Algorithm, Step by Step#

Phase 1 — Divide: Split nums into a left half and a right half. Recursively sort each half and count reverse pairs within each half. By induction, when we return from the recursive calls, both halves are sorted and we have an accurate count of all pairs where both i and j fall inside the same half.

Phase 2 — Count cross-pairs (BEFORE merging): At this point, both halves are sorted. We need to count pairs where i falls in the left half and j falls in the right half. Because both halves are already sorted, we can use two pointers efficiently:

• For each element x in the left half (in order), advance a pointer r in the right half as long as x > 2 * right[r].
• All r elements we passed satisfy the reverse pair condition with x.
• Because the left half is sorted in ascending order, if x > 2 * right[r] then any later element x' (which is >= x) also satisfies x' > 2 * right[r]. So the pointer r never needs to go backwards. This gives an O(n) count pass.

Phase 3 — Merge (AFTER counting): Now perform the standard merge sort merge to produce a sorted combined array. This sorted array is what the parent call will use during its own count phase. If you merged before counting, the relative ordering of left and right elements would be destroyed, and the two-pointer count would be meaningless.

Why does counting before merging work? Because the condition nums[i] > 2 * nums[j] only cares about the values of elements, not their positions after merging. As long as we know which elements came from the left half and which from the right half, we can count before merging. After we merge, the distinction between "left" and "right" is gone forever, which is exactly why counting must come first.

Visual Dry Run#

Let us trace through nums = [1, 3, 2, 3, 1] step by step.

Step 1 — Recursive decomposition#

[1, 3, 2, 3, 1]
     /        \
 [1, 3]     [2, 3, 1]
  /   \       /    \
[1]  [3]   [2]   [3, 1]
                  /    \
                [3]    [1]

Step 2 — Base cases (single elements)#

All single-element arrays have 0 reverse pairs and are trivially sorted.

Step 3 — Merge [3] and [1]#

Count pass: Is 3 > 2 * 1 = 2? Yes. Count += 1. Pointer moves past [1]. Merge pass: 1 <= 3, so pick 1 first → [1, 3].

Running count: 1.

Step 4 — Merge [2] and [1, 3]#

Count pass (left = [2], right = [1, 3]):

• x = 2: Is 2 > 2 * 1 = 2? No (not strictly greater). Pointer r stays at 0. Count += 0.
• No more elements in left.

Count from this level: 0. Running total: 1.

Merge pass: Compare 2 vs 1 → pick 1. Compare 2 vs 3 → pick 2. Append 3. Result: [1, 2, 3].

Step 5 — Merge [1] and [3]#

Count pass: Is 1 > 2 * 3 = 6? No. Count += 0. Merge pass: 1 <= 3 → [1, 3].

Running total: 1.

Step 6 — Merge [1, 3] and [1, 2, 3]#

Count pass (left = [1, 3], right = [1, 2, 3]):

• x = 1: Is 1 > 2 * 1 = 2? No. Pointer r stays at 0. Count += 0.
• x = 3: Is 3 > 2 * 1 = 2? Yes, advance r to 1. Is 3 > 2 * 2 = 4? No, stop. Count += 1 (r=1, so 1 element in right satisfies the condition).

Count from this level: 1. Running total: 2.

Merge pass: Standard merge of [1,3] and [1,2,3] → [1, 1, 2, 3, 3].

Final Answer: 2 ✓#

Common Mistakes#

Mistake 1 — Counting during the merge instead of before it#

This is the most common and most damaging mistake. Consider left = [3] and right = [1]. If you try to count while merging:

• You compare 3 and 1, pick 1 (since 1 < 3), and try to say "3 forms a reverse pair with 1."
• But the merge step has already re-ordered elements. If the left had [1, 3] and right [1, 2], counting during merging would mix up which elements you have already processed.

Fix: Always do two separate loops — one to count, one to merge.

Mistake 2 — Using strict greater than in the merge step#

The merge condition is left[i] <= right[k] (stable sort). Some candidates write left[i] < right[k] (strict less than), which produces an unstable sort and can cause incorrect counts on future levels.

Fix: Use <= in the merge comparison, not <.

Mistake 3 — Integer overflow when computing 2 * nums[j]#

The constraint says nums[i] can be up to 2^31 - 1. Doubling that overflows a 32-bit integer. In languages with fixed-size integers (C++, Java), this silently wraps around and produces wrong comparisons. In Python this is not an issue (arbitrary precision), but in JavaScript 2 * nums[j] can lose precision for very large integers.

Fix (JavaScript): Use BigInt for the comparison, or verify that inputs stay within safe integer range. For the LeetCode constraints, nums[i] fits in a 32-bit signed integer, so 2 * nums[j] fits in a 64-bit integer — JavaScript's Number type (64-bit float) can represent integers up to 2^53 exactly, so for this problem's constraints it is safe.

Mistake 4 — Re-using the pointer r across left elements incorrectly#

The pointer r should start at 0 and only advance — it should never reset between elements of the left half. Some candidates reset r = 0 for each element of the left half, turning the count pass into O(n^2) instead of O(n).

Fix: Initialise r = 0 once before the loop over left elements, and only advance it forward.

Mistake 5 — Applying the wrong condition: >= instead of >#

The problem says nums[i] > 2 * nums[j] (strictly greater than). Some candidates write nums[i] >= 2 * nums[j], overcounting pairs. For example, [1, 2] should give 0 (since 1 > 2*2=4 is false), but with >= you would also count pairs where nums[i] == 2 * nums[j].

Fix: Use strict > in the count condition.

Solutions#

Brute Force — O(n^2)#

Useful for verifying correctness on small inputs during an interview. Always start here to confirm your understanding of the problem before optimising.

Python — Brute Force#

def reversePairs_brute(nums: list[int]) -> int:
    """
    Check every pair (i, j) with i < j.
    Time: O(n^2)   Space: O(1)
    Correct but will time-out for n > ~10,000.
    """
    count = 0
    n = len(nums)
 
    for i in range(n):
        for j in range(i + 1, n):
            # Check the reverse pair condition strictly
            if nums[i] > 2 * nums[j]:
                count += 1
 
    return count

JavaScript — Brute Force#

/**
 * Brute force: check every pair.
 * Time: O(n^2)   Space: O(1)
 *
 * @param {number[]} nums
 * @return {number}
 */
function reversePairs_brute(nums) {
    let count = 0;
    const n = nums.length;
 
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            // Strictly greater than double — not >=
            if (nums[i] > 2 * nums[j]) {
                count++;
            }
        }
    }
 
    return count;
}

Optimal — Modified Merge Sort — O(n log n)#

Python — Merge Sort#

def reversePairs(nums: list[int]) -> int:
    """
    Modified merge sort: count cross-half reverse pairs BEFORE merging.
    Time: O(n log n)   Space: O(n) for the auxiliary arrays at each level.
    """
 
    def merge_sort(arr: list[int]) -> tuple[list[int], int]:
        # Base case: a single element is already sorted with 0 pairs
        if len(arr) <= 1:
            return arr, 0
 
        # Divide the array into two halves
        mid = len(arr) // 2
        left, left_count  = merge_sort(arr[:mid])    # recursively sort left half
        right, right_count = merge_sort(arr[mid:])   # recursively sort right half
 
        # Start with the counts accumulated from both halves
        count = left_count + right_count
 
        # --- PHASE 1: Count cross-half reverse pairs (BEFORE merging) ---
        # Both halves are sorted. Use two pointers to count in O(n).
        # For each x in left, advance r while x > 2 * right[r].
        # All elements right[0..r-1] satisfy the condition with x.
        # Because left is sorted ascending, r never needs to go backward.
        r = 0
        for x in left:
            while r < len(right) and x > 2 * right[r]:
                r += 1          # right[r] is too large; move on
            count += r          # r elements in right satisfy x > 2 * right[j]
 
        # --- PHASE 2: Standard merge (AFTER counting) ---
        # This produces the sorted combined array for the parent call.
        merged = []
        i, k = 0, 0
 
        while i < len(left) and k < len(right):
            # Use <= for stability; do NOT use < here
            if left[i] <= right[k]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[k])
                k += 1
 
        # Append any remaining elements from either half
        merged.extend(left[i:])
        merged.extend(right[k:])
 
        return merged, count
 
    _, total = merge_sort(nums)
    return total

JavaScript — Merge Sort#

/**
 * Modified merge sort to count reverse pairs.
 * Key insight: count cross-half pairs BEFORE the merge step,
 * not during it — mixing the two operations produces wrong results.
 *
 * Time: O(n log n)   Space: O(n)
 *
 * @param {number[]} nums
 * @return {number}
 */
function reversePairs(nums) {
 
    /**
     * Recursively sort arr and return [sortedArr, pairCount].
     * @param {number[]} arr
     * @return {[number[], number]}
     */
    function mergeSort(arr) {
        // Base case: a single element needs no sorting and has no pairs
        if (arr.length <= 1) return [arr, 0];
 
        // Split into two halves
        const mid = Math.floor(arr.length / 2);
        const [left,  leftCount]  = mergeSort(arr.slice(0, mid));  // sort left half
        const [right, rightCount] = mergeSort(arr.slice(mid));     // sort right half
 
        // Accumulate counts from both halves
        let count = leftCount + rightCount;
 
        // --- PHASE 1: Count cross-half reverse pairs (BEFORE merging) ---
        // Both halves are now sorted ascending.
        // For each x in left, advance r while x > 2 * right[r].
        // The pointer r only moves forward — total work across all x is O(n).
        let r = 0;
        for (const x of left) {
            while (r < right.length && x > 2 * right[r]) {
                r++;            // right[r] still qualifies — keep advancing
            }
            count += r;         // all right[0..r-1] form reverse pairs with x
        }
 
        // --- PHASE 2: Standard merge (AFTER counting) ---
        // Produce the sorted combined array so the parent call can count correctly.
        const merged = [];
        let i = 0, k = 0;
 
        while (i < left.length && k < right.length) {
            // Stable merge: use <= so equal elements from left come first
            if (left[i] <= right[k]) {
                merged.push(left[i++]);
            } else {
                merged.push(right[k++]);
            }
        }
 
        // Drain remaining elements from whichever half is not exhausted
        while (i < left.length)  merged.push(left[i++]);
        while (k < right.length) merged.push(right[k++]);
 
        return [merged, count];
    }
 
    const [, total] = mergeSort(nums);
    return total;
}

Complexity Analysis#

Time — merge sort: The recursion splits the array log n times. At each level, the count pass and the merge pass each do O(n) total work across all sub-problems at that level (the two-pointer never backtracks). So total time is O(n log n).

Space — merge sort: Each call allocates a merged array equal in size to the current sub-problem. At any point in the recursion, the total allocated space across all active frames is O(n) (the levels form a binary tree, and sibling calls do not overlap). The call stack depth is O(log n). Overall space is O(n).

Why not O(1) space? In-place merge sort exists but is significantly more complex and does not cleanly support the "count before merge" two-pointer pattern. For an interview, O(n) space is the expected and accepted answer.

Follow-up Questions#

Interviewers at Google and Amazon commonly extend this problem in one of three directions:

1. Count of Smaller Numbers After Self (LeetCode 315) This is the direct sibling problem: count, for each element nums[i], how many elements to its right are strictly smaller. The same modified merge sort approach applies — during the count phase, instead of accumulating a single total, you record per-element counts. This problem is frequently asked at Google.

2. Binary Indexed Tree / Fenwick Tree approach Instead of merge sort, you can coordinate-compress the values of nums and use a BIT to answer "how many values inserted so far are at most v" in O(log n) time. For each element nums[j], query the BIT for values <= nums[j] / 2 (adjusted for the > 2 * condition), then insert nums[j]. The total time is O(n log n). This is the approach preferred in competitive programming. Understanding merge sort first makes the BIT approach intuitive — both are counting elements in a range, just with different data structures.

3. Range Sum Query — Count of Range Sum (LeetCode 327) Count subarray sums that fall in a given range [lower, upper]. This problem uses the exact same modified merge sort framework: divide into halves, count cross-half qualifying sums using two pointers on prefix-sum arrays, then merge. If you can solve Reverse Pairs, LeetCode 327 is a natural extension that requires one additional insight (prefix sums), but the structural template is identical.

This Pattern Solves#

Once you internalise the "count cross-half interactions before merging" pattern, you will recognise it across a family of problems:

• Count of inversions — pairs (i, j) with i < j and nums[i] > nums[j]. Same merge sort structure with condition > instead of > 2 *.
• Count of smaller numbers after self (LC 315) — per-element version of inversion count.
• Count of range sums (LC 327) — count prefix-sum pairs in a range using the same divide step.
• Closest pair of points — geometry problem where you count cross-strip pairs in O(n) after sorting by y-coordinate within each strip.

The unifying principle: divide-and-conquer is powerful when "cross-boundary interactions" can be counted efficiently given that sub-problems are already solved (sorted). The sorted invariant is what makes the two-pointer count O(n) instead of O(n^2).

Key Takeaways#

• Reverse Pairs (LC 493) counts pairs (i, j) with i < j and nums[i] > 2 * nums[j] — a harder variant of the classic inversion count.
• The > 2 * condition breaks the single-pass merge-sort inversion trick: you must count before you merge, because the modified condition does not produce merge-sort order.
• The count step uses a two-pointer scan on sorted halves in O(n) — only advance j when nums[i] > 2 * nums[j] no longer holds; all prior j positions count for this i.
• The merge step is a separate, standard stable merge that runs after counting — never combine these two passes into one.
• Always sort index-value pairs (or use a parallel index array) so you can write back counts to the correct position.
• O(n log n) time, O(n) space; the three-step template is: divide, count cross-half pairs, merge.
• This problem is part of a family: LC 315 (Count Smaller After Self), LC 327 (Count of Range Sum) all use the same "count cross-half during divide-and-conquer" skeleton.