← DSA Atlas
Dedicated problem page · #493

Reverse Pairs

HardAdvanced Range Data StructuresCount significant inversionsMerge sort with cross-pair counting
Solve on LeetCode ↗
493
HardAdvanced Range Data StructuresMerge sort with cross-pair countingCount significant inversions

Reverse Pairs

Given an integer array nums, return the number of reverse pairs. A reverse pair is a pair (i, j) where i < j and nums[i] > 2 * nums[j].

Open official problem prompt ↗
In plain English

Count how many ordered pairs have a left value more than double the right value, across the whole array.

Picture it like this

Imagine ranking cars by resale value. A reverse pair is an early car worth more than twice a later one. Sorting each half of the timeline lets you tally, for each pricey early car, how many cheap later cars it dwarfs, without checking every combination.

Example
Input
nums = [1,3,2,3,1]
Output
2
Why
The reverse pairs are (1,4): 3 > 2*1, and (3,4): 3 > 2*1; no other pair satisfies nums[i] > 2*nums[j].
Constraints
1 <= nums.length <= 5 * 10^4-2^31 <= nums[i] <= 2^31 - 1
Pattern lesson

See the pattern, then code

Count significant inversions
Recognition clue

Counting ordered pairs where a left value exceeds a scaled right value is a significant-inversion count, solvable by augmenting merge sort or by a Fenwick tree over ranks.

↗
Advanced Range Data Structures

Online prefix or range queries with updates, inversions, or coordinate compression.. During merge sort, once both halves are sorted, count for each left element how many right elements satisfy nums[left] > 2 * nums[right]. Sorted order lets a single advancing pointer tally these before the normal merge.

New words, made simpleKnow these before the algorithm
Reverse pair
Indices i < j with nums[i] > 2 * nums[j].
Significant inversion
A generalized inversion using a scaling factor (here 2) instead of a plain greater-than.
Stable merge
Combining two sorted halves while preserving order, used to keep the array sorted for parent calls.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Brute force pairs

Too slow for n = 5 * 10^4.

Test every pair (i, j) with i < j.

Time O(n^2)Space O(1)
Best choiceMerge sort counting

Clean, handles negatives and the doubling without overflow in Python.

Count cross-half reverse pairs while merging, using sorted halves.

Time O(n log n)Space O(n)
Fenwick tree over ranks

Works but coordinate compression with the 2x factor is fiddly.

Insert values and query how many earlier values exceed 2x each new value using compressed ranks.

Time O(n log n)Space O(n)
The rule we keep true

Invariant

By the time a merge combines two sorted halves, count already contains all reverse pairs internal to each half; the counting sweep adds exactly the pairs whose left index is in the lower half and right index in the upper half.

Why this is correct

Reasoning

Each reverse pair has a unique split point where its two indices first fall into different halves of the recursion; the counting loop processes that pair once at that level. Because the right half is sorted, the pointer j marking values satisfying nums[i] > 2 * nums[j] only moves forward as i increases within a sorted left half, so counting is linear per level and correct.

The algorithm in three movesSay these aloud before coding
1Recursively split the array and count reverse pairs inside each half

left [1,3], right [2,3,1] recurse

2With both halves sorted, sweep a pointer j over the right half for each left element

sorted halves compared at boundary

3Advance j while nums[i] > 2 * nums[j], adding j - mid to the count

3 > 2*1 twice

4Sort the combined slice for the parent call

total = 2

5Return the accumulated count

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
31
22
33
14
1 · Read[1,3,2,3,1]
2 · AskHalves?
3 · Update stateleft [1,3], right [2,3,1]
4 · Resultrecurse both
Key takeaway

Both halves sorted; each left value counts how many right values it more than doubles.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 4-8Divide

    Split the slice and recursively count reverse pairs contained entirely within each half.

  2. 2
    Lines 9-13Count across boundary

    For each left element, advance j over the sorted right half while the doubling condition holds and add the span.

  3. 3
    Lines 14Merge (sort slice)

    Re-sort the slice so the parent merge sees sorted input; counting was done before this destroys index order.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single element returns 0
  • All increasing values give 0 reverse pairs
  • Negative values: e.g. nums[i]=-1, nums[j]=-3 gives -1 > -6 true, so negatives can form pairs
  • Large values near 2^31 need the 2 * nums[j] computed without 32-bit overflow (safe in Python)
!

Common beginner mistakes

  • Counting during the same loop that merges, which corrupts the count because merging reorders elements mid-count
  • Using >= instead of > in the 2 * nums[j] condition
  • Resetting pointer j for each left element instead of keeping it monotonic
  • Overflow of 2 * nums[j] in fixed-width languages; guard by comparing nums[i]/2.0 or using 64-bit
Check your understanding

Why is the reverse-pair counting done in a separate loop before merging the two halves?

More in Advanced Range Data Structures

#218The Skyline ProblemSweep line with max-heap#307Range Sum Query – MutablePoint update, prefix-sum query#315Count of Smaller Numbers After SelfCount smaller to the right#327Count of Range SumCount prefix-sum pairs in range#699Falling SquaresRange assign, range max#715Range ModuleMerge and split disjoint intervals