LeetCode #493 Hard

Reverse Pairs

Count pairs (i, j) with i < j and nums[i] > 2 * nums[j].

arraymerge-sortdivide-and-conquer

02

Intuition

Checking every pair is O(n²). Merge sort already compares the left half against the right half while sorting — piggyback on it. When both halves are sorted, for each left element the right-half values that violate the condition form a prefix, so a two-pointer sweep counts all cross pairs in linear time per level.

How to spot this pattern

Count-inversions with a twist — the condition nums[i] > 2 nums[j] isn't the same as the merge comparison, so the counting can't ride along inside the merge itself. It needs its own two-pointer sweep over the two sorted halves before* merging. Recognising when a counting condition diverges from the sort order is what tells you to separate the passes.

03

Approach

1

Divide

Split the array in half; count pairs entirely inside each half recursively. What's left is pairs that cross the middle.

2

Count cross pairs on sorted halves

With both halves sorted, walk a pointer j over the right half for each left i: advance j while nums[i] > 2*nums[j]. j never moves backward, so the count for the whole level is O(n).

3

Merge as usual

After counting, restore sorted order so the parent call sees a sorted range. The code delegates this to Python's sorted(): because the two halves are already sorted, Timsort detects the runs and merges them in linear time, so the level stays O(n) — an explicit two-pointer merge would be equivalent. Sorting doesn't lose pairs, since counting happened before the order changed across the boundary.

04

Solution & live demo

▶1class Solution:
▶2    def reversePairs(self, nums):
▶3        def sort(lo, hi):
▶4            if hi - lo <= 1: return 0
▶5            mid = (lo + hi) // 2
▶6            count = sort(lo, mid) + sort(mid, hi)
▶7            j = mid
▶8            for i in range(lo, mid):
▶9                while j < hi and nums[i] > 2 * nums[j]:
▶10                    j += 1
▶11                count += j - mid
▶12            nums[lo:hi] = sorted(nums[lo:hi])
▶13            return count
▶14        return sort(0, len(nums))

05

Common pitfalls

Counting inside the merge comparison

✗ Wrong

if left[i] <= right[j]:
    merged.append(left[i]); i += 1
else:
    count += len(left) - i

✓ Right

j = mid
for i in range(lo, mid):
    while j < hi and nums[i] > 2 * nums[j]: j += 1
    count += j - mid

That counts pairs where left[i] > right[j], not where left[i] > 2 * right[j] — a strictly different and much larger set. The doubled condition needs a separate sweep before the halves are merged.

Resetting the right pointer for each left element

✗ Wrong

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

✓ Right

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

Both halves are sorted, so a larger nums[i] can only push j further right — it never moves back. Resetting makes the sweep O(n²) per merge instead of O(n).

Counting after sorting the range

✗ Wrong

nums[lo:hi] = sorted(nums[lo:hi])
# then count

✓ Right

# count across the two sorted halves
nums[lo:hi] = sorted(nums[lo:hi])

Once the range is merged, the split between left and right is gone and you can no longer tell which element came from which half — only cross-half pairs count as reverse pairs. Count first, merge second.

06

Edge cases

Negative numbers

2*nums[j] handles signs fine; comparisons stay valid on sorted halves.

Overflow in other languages

2× a large int needs 64 bits; Python is safe.

07

Complexity

Time

O(n log n)

Space

O(n)

Merge-sort recursion; counting per level is linear.