LeetCode 493 - Reverse Pairs

The problem asks us to count how many pairs of indices (i, j) satisfy two conditions: 1. i < j 2. nums[i] 2 nums[j] These pairs are called reverse pairs.

leetcodehardarraybinary-searchdivide-and-conquerbinary-indexed-treesegment-treemerge-sortordered-set

LeetCode Problem 493

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set

Solution

Problem Understanding

The problem asks us to count how many pairs of indices (i, j) satisfy two conditions:

  1. i < j
  2. nums[i] > 2 * nums[j]

These pairs are called reverse pairs.

Unlike the classic inversion count problem, where we check whether nums[i] > nums[j], this problem uses a stricter condition involving multiplication by two. That extra condition changes the behavior significantly and prevents us from using some simpler inversion counting tricks directly.

The input is an integer array nums, and the output is a single integer representing the total number of valid reverse pairs.

The constraints are important:

  • nums.length can be as large as 5 * 10^4
  • Values can range from -2^31 to 2^31 - 1

A brute force solution would need to examine every pair (i, j), which would require O(n^2) time. With 50,000 elements, that would mean roughly 2.5 billion comparisons in the worst case, which is far too slow.

The value range also matters because multiplying by 2 can overflow 32-bit integers in some languages like Go or Java. We must be careful to use larger integer types when performing comparisons such as:

nums[i] > 2 * nums[j]

Some important edge cases include:

  • Arrays with all equal numbers
  • Arrays with negative numbers
  • Arrays already sorted ascending or descending
  • Arrays containing extremely large positive or negative integers
  • Very small arrays such as length 1

Negative values are especially tricky because multiplication by 2 changes ordering behavior in unintuitive ways. For example:

-1 > 2 * -3
-1 > -6

This is true, so reverse pairs can exist even when values are negative.

Approaches

Brute Force Approach

The most direct solution is to check every possible pair (i, j) where i < j.

For each pair:

  • Compute whether nums[i] > 2 * nums[j]
  • If true, increment the answer

This approach is guaranteed to be correct because it explicitly evaluates every valid pair.

However, the time complexity is O(n^2) because there are roughly n * (n - 1) / 2 pairs. With 50,000 elements, this becomes computationally infeasible.

Optimal Approach, Merge Sort Based Counting

The key insight is that this problem resembles inversion counting, which can be solved efficiently using merge sort.

Merge sort recursively divides the array into sorted halves. Once two halves are individually sorted, we can efficiently count cross-half reverse pairs.

Suppose:

  • Left half is sorted
  • Right half is sorted

For each value in the left half, we want to count how many values in the right half satisfy:

left_value > 2 * right_value

Because both halves are sorted, we can use a two-pointer technique to count these pairs in linear time during the merge step.

This transforms the total complexity from O(n^2) to O(n log n).

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Checks every pair directly
Optimal Merge Sort O(n log n) O(n) Counts reverse pairs during merge sort

Algorithm Walkthrough

Optimal Merge Sort Algorithm

  1. Divide the array into two halves recursively until each subarray contains one element.

A single element cannot form a reverse pair by itself, so these are trivially sorted. 2. Recursively solve the left half.

This returns:

  • The number of reverse pairs inside the left half
  • The left half in sorted order
  1. Recursively solve the right half.

Similarly, this returns:

  • The number of reverse pairs inside the right half
  • The right half in sorted order
  1. Count reverse pairs across the two halves.

At this point:

  • Left half is sorted
  • Right half is sorted

Use two pointers:

  • i traverses the left half
  • j traverses the right half

For each nums[i], advance j while:

nums[i] > 2 * nums[j]

Since the right half is sorted, once a value satisfies the condition, all earlier values also satisfy it.

The number of valid pairs contributed by nums[i] is:

j - (mid + 1)
  1. Merge the two sorted halves.

Perform the standard merge operation from merge sort so that the current segment becomes sorted. 6. Return the total count.

The final answer equals:

left_count + right_count + cross_count

Why it works

The correctness relies on the fact that merge sort guarantees both halves are sorted before the counting phase begins.

Because the halves are sorted:

  • If nums[i] > 2 * nums[j] for some j,
  • Then it is also true for all earlier elements in the right half.

This monotonic behavior allows the two-pointer scan to count all valid pairs efficiently without revisiting elements repeatedly.

Every reverse pair belongs to exactly one of these categories:

  • Entirely in the left half
  • Entirely in the right half
  • Crossing between halves

The recursion counts all three categories exactly once.

Python Solution

from typing import List

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def merge_sort(left: int, right: int) -> int:
            if left >= right:
                return 0

            mid = (left + right) // 2

            count = merge_sort(left, mid)
            count += merge_sort(mid + 1, right)

            # Count reverse pairs
            j = mid + 1

            for i in range(left, mid + 1):
                while j <= right and nums[i] > 2 * nums[j]:
                    j += 1

                count += j - (mid + 1)

            # Merge step
            merged = []
            p1 = left
            p2 = mid + 1

            while p1 <= mid and p2 <= right:
                if nums[p1] <= nums[p2]:
                    merged.append(nums[p1])
                    p1 += 1
                else:
                    merged.append(nums[p2])
                    p2 += 1

            while p1 <= mid:
                merged.append(nums[p1])
                p1 += 1

            while p2 <= right:
                merged.append(nums[p2])
                p2 += 1

            nums[left:right + 1] = merged

            return count

        return merge_sort(0, len(nums) - 1)

The implementation follows the merge sort structure closely.

The merge_sort function recursively sorts a subarray and returns the number of reverse pairs within that range.

The recursive calls first process the left and right halves independently. Once both halves are sorted, the algorithm counts cross-half reverse pairs using a two-pointer scan.

The pointer j only moves forward, never backward. This is important because it guarantees linear work during each merge phase.

After counting, the code performs the standard merge operation to maintain sorted order. The merged result replaces the original segment in nums.

Finally, the total reverse pair count is returned.

Go Solution

func reversePairs(nums []int) int {
	var mergeSort func(int, int) int

	mergeSort = func(left int, right int) int {
		if left >= right {
			return 0
		}

		mid := (left + right) / 2

		count := mergeSort(left, mid)
		count += mergeSort(mid+1, right)

		// Count reverse pairs
		j := mid + 1

		for i := left; i <= mid; i++ {
			for j <= right && int64(nums[i]) > 2*int64(nums[j]) {
				j++
			}

			count += j - (mid + 1)
		}

		// Merge step
		temp := make([]int, 0, right-left+1)

		p1 := left
		p2 := mid + 1

		for p1 <= mid && p2 <= right {
			if nums[p1] <= nums[p2] {
				temp = append(temp, nums[p1])
				p1++
			} else {
				temp = append(temp, nums[p2])
				p2++
			}
		}

		for p1 <= mid {
			temp = append(temp, nums[p1])
			p1++
		}

		for p2 <= right {
			temp = append(temp, nums[p2])
			p2++
		}

		for i := 0; i < len(temp); i++ {
			nums[left+i] = temp[i]
		}

		return count
	}

	return mergeSort(0, len(nums)-1)
}

The Go implementation is structurally similar to the Python version, but there are some language-specific details worth noting.

The most important difference is integer overflow handling. Since nums[i] may be close to the 32-bit limit, the comparison:

nums[i] > 2 * nums[j]

could overflow if performed using normal int arithmetic.

To avoid this, the implementation converts values to int64 before multiplication:

int64(nums[i]) > 2 * int64(nums[j])

The merge step uses slices to build a temporary merged array, which is then copied back into the original array segment.

Go slices are dynamic, so append is used during merging.

Worked Examples

Example 1

Input:

[1,3,2,3,1]

Recursive Division

[1,3,2] and [3,1]

Then:

[1,3] and [2]
[3] and [1]

Counting Cross Pairs

When merging:

Left:  [1,2,3]
Right: [1,3]

We check each left element against the right side.

Left Value Right Pointer Movement Valid Pairs Added
1 none 0
2 none 0
3 moves past 1 1

Earlier recursive merges already found another reverse pair:

(3,1)

Total:

2

Example 2

Input:

[2,4,3,5,1]

Final Merge Stage

Sorted halves:

Left:  [2,3,4]
Right: [1,5]

Counting

Left Value Condition Checks Pairs Added
2 2 > 2*1 is false 0
3 3 > 2*1 is true 1
4 4 > 2*1 is true 1

Another reverse pair comes from:

5 > 2*1

Total:

3

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Merge sort performs log n levels, each processing n elements
Space O(n) Temporary arrays are used during merging

At every recursion level, the algorithm processes all elements once during counting and merging.

Since merge sort has log n levels, the total complexity becomes:

O(n log n)

The extra space comes from the temporary merged arrays used during merge operations.

Test Cases

sol = Solution()

# Provided examples
assert sol.reversePairs([1, 3, 2, 3, 1]) == 2  # basic example
assert sol.reversePairs([2, 4, 3, 5, 1]) == 3  # another standard example

# Single element
assert sol.reversePairs([1]) == 0  # no pairs possible

# Two elements with reverse pair
assert sol.reversePairs([5, 2]) == 1  # 5 > 2*2

# Two elements without reverse pair
assert sol.reversePairs([2, 2]) == 0  # equal values

# Sorted ascending
assert sol.reversePairs([1, 2, 3, 4, 5]) == 0  # no reverse pairs

# Sorted descending
assert sol.reversePairs([5, 4, 3, 2, 1]) == 4  # several reverse pairs

# All zeros
assert sol.reversePairs([0, 0, 0, 0]) == 0  # no strict inequality

# Negative numbers
assert sol.reversePairs([-5, -5]) == 1  # -5 > 2*(-5)

# Mixed positive and negative
assert sol.reversePairs([-5, -2, -1, 0, 3]) == 0  # no valid pairs

# Large values near integer limits
assert sol.reversePairs([2147483647, 1, 0]) == 3  # overflow-sensitive case

# Duplicate values
assert sol.reversePairs([2, 2, 2, 2]) == 0  # duplicates

# Stress style pattern
assert sol.reversePairs([10, 5, 2, 1]) == 4  # multiple cascading pairs

Test Summary

Test Why
[1,3,2,3,1] Verifies standard example
[2,4,3,5,1] Verifies another common case
[1] Smallest possible array
[5,2] Single reverse pair
[2,2] Equality should not count
[1,2,3,4,5] No reverse pairs
[5,4,3,2,1] Many reverse pairs
[0,0,0,0] Strict inequality validation
[-5,-5] Negative number handling
[-5,-2,-1,0,3] Mixed signed values
[2147483647,1,0] Integer overflow safety
[2,2,2,2] Duplicate values
[10,5,2,1] Stresses merge counting logic

Edge Cases

One important edge case is arrays containing negative numbers. Many implementations incorrectly assume reverse pairs mostly occur with large positive values. However, negative values can also satisfy the condition because multiplying by two makes them even smaller. For example:

-5 > 2 * -5
-5 > -10

This is true. The merge sort solution handles negative values naturally because it relies only on comparisons and sorted ordering.

Another critical edge case involves integer overflow. If nums[j] is close to the 32-bit integer limit, computing 2 * nums[j] may overflow in some languages. The Go implementation explicitly converts values to int64 before multiplication to avoid incorrect comparisons. Python integers automatically expand, so Python does not have this issue.

A third important edge case is arrays with many duplicate values. Since the condition is strictly greater than:

nums[i] > 2 * nums[j]

equal values should not count unless the multiplication condition truly holds. For example:

[2,2,2,2]

contains zero reverse pairs. The implementation correctly preserves strict inequality during counting.

Another subtle case is already sorted ascending arrays. A naive inversion-count mindset might expect some pairs to exist, but for strictly increasing arrays, reverse pairs are often absent because later elements are not small enough to satisfy the factor-of-two condition. The algorithm correctly returns zero for such cases.