Reverse Pairs

You're given an integer array nums. A pair of indices (i, j) is called a reverse pair when:

0 <= i < j < nums.length, and
nums[i] > 2 * nums[j] — the earlier value is more than twice the later one.

Return the total number of reverse pairs in nums.

Note that the condition is strict (>), and it compares against double the later value — nums[i] > nums[j] alone is not enough.

Hints

· Stuck? Reveal one nudge at a time.

Counting all pairs one by one costs O(n²) — too slow for n = 5 * 10^4. Which classic sorting algorithm naturally splits the array into two halves and visits every cross-half relationship?

Split the array at the middle. Any pair with i in the left half and j in the right half keeps i < j no matter how each half is internally reordered — so you're free to sort the halves before counting cross pairs.

With both halves sorted, walk the left half once while a pointer sweeps the right half forward: once nums[i] > 2 * nums[j], every larger left element also beats nums[j], so the pointer never resets. Count with this sweep, then do a standard merge — count first, merge second.

Common doubts

The merge decides order with nums[i] <= nums[k], but the pair condition here is nums[i] > 2 * nums[j] — two different tests. When the merge pops an element you learn nothing about the doubled condition, so counting mid-merge silently miscounts. Run a dedicated counting sweep first, then merge.

Only when they're negative. x > 2 * x is false for x >= 0 but true for x < 0 — for example [-5, -5] contains one reverse pair, since -5 > -10.

In 32-bit arithmetic, yes — nums[j] can be 2^31 - 1, so doubling it leaves the 32-bit range. In C++ compare as (long long)nums[i] > 2LL * nums[j]. Python, JavaScript, and Go's 64-bit int handle it natively.

No — the definition only needs i < j, and every index in the left half is smaller than every index in the right half regardless of how the halves are shuffled internally. Pairs within a half are counted by the recursive calls before that half was sorted at this level.

Interview follow-ups

· What an interviewer asks next.

Yes. Coordinate-compress the values of nums together with their doubles, sweep j from left to right, and before inserting nums[j] query how many already-seen values exceed 2 * nums[j]. Same O(n log n) time; it's the go-to shape when elements arrive one at a time.

The count-then-merge skeleton is unchanged — only the while condition becomes nums[i] > k * nums[j]. The sweep stays valid because the predicate is still monotone over the sorted halves.

Maintain a Binary Indexed Tree (or balanced BST) over compressed values: for each new element x, add the count of previously seen values greater than 2x, then insert x. That's O(log n) per element.

Fun facts

This is Count Inversions with the comparison tightened from bigger to more-than-double — and that tiny change breaks the beloved count-during-merge trick, forcing the cleaner and more general count-then-merge pattern.
The forward-only counting sweep reappears almost verbatim in Count of Smaller Numbers After Self and Count of Range Sum — all three are merge sort counting in disguise, differing only in the while condition.
The answer itself needs care: with n = 5 * 10^4 the count can reach about 1.25 * 10^9, which still fits a 32-bit int — but only barely; the k-times variant of this problem can push it past.

Asked at

GoogleAmazonMicrosoftUberAdobe

Frequently Sometimes Occasionally

Example 1

Input: nums = [1,3,2,3,1]
Output: 2
Two reverse pairs: (1, 4) since nums[1] = 3 > 2 * nums[4] = 2, and (3, 4) since nums[3] = 3 > 2 * nums[4] = 2.

Example 2

Input: nums = [2,4,3,5,1]
Output: 3
Three reverse pairs, all against nums[4] = 1: (1, 4) with 4 > 2, (2, 4) with 3 > 2, and (3, 4) with 5 > 2.

Example 3

Input: nums = [-5,-5]
Output: 1
-5 > 2 * (-5) = -10, so (0, 1) counts — equal negative values can form a reverse pair.

Constraints

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

Reverse Pairs is Count Inversions with the volume turned up: instead of asking how many earlier elements are merely bigger than a later one, it asks how many are more than double. That one-word change breaks the classic count-during-merge shortcut — and teaches the cleanest, most reusable form of merge sort counting, a pattern that unlocks a whole family of hard counting problems.

Prerequisites

Before you start

· Concepts used directly in the solution.

Merge sort. The divide, conquer, merge skeleton — we piggyback the pair count on it.

Two pointers on sorted arrays. A pointer that only moves forward, because sortedness makes the condition monotone.

Divide and conquer complexity. Why O(n) work per level across log n levels gives O(n log n).

Integer overflow. Doubling a 32-bit value can leave the 32-bit range — compare in 64 bits.

Understand the problem

Plain English: for every pair of positions (i, j) with i before j, check whether nums[i] > 2 * nums[j], and count how many pairs pass.

Formally: given an integer array nums, return the number of index pairs (i, j) such that 0 <= i < j < nums.length and nums[i] > 2 * nums[j].

Worked example — nums = [1, 3, 2, 3, 1]

index:  0  1  2  3  4
value:  1  3  2  3  1

(i=1, j=4): 3 > 2*1 = 2   ✓
(i=3, j=4): 3 > 2*1 = 2   ✓
every other pair fails

answer: 2

Clarifying questions

Two or three sharp questions before coding show you probe guarantees instead of assuming them — and this problem hides real traps in its value range.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Can values be negative or repeated?”

Yes to both — and it matters. For a negative x, x > 2 * x is true, so two equal negatives like [-5, -5] form a reverse pair.

“Can 2 * nums[j] overflow a 32-bit integer?”

Yes — values reach 2^31 - 1, so the doubling can leave the 32-bit range. Widen to 64 bits before comparing.

Edge cases

“What do I return for a single-element array?”

0 — a pair needs two distinct indices.

“Do equal values like [5, 5] ever count?”

Not when non-negative: 5 > 10 is false. Only equal negatives count.

Constraints and scale

“How large can the array get?”

Up to 5 * 10^4 elements — about 1.25 * 10^9 pairs, so checking each pair individually is off the table.

The ideal opening — say it like this

Before I code, I want to confirm the input guarantees.

Values can be negative and repeated — and since x is greater than 2x when x is negative, equal negatives do form reverse pairs.

Values reach 2^31 - 1, so I will widen 2 * nums[j] to 64 bits before comparing.

With n up to 5 * 10^4, checking every pair is too slow, so I am aiming for merge sort counting in O(n log n).

Key observations

1Aha

Cross pairs survive any shuffle inside the halves

Split the array at mid. For any i in the left half and j in the right half, i < j holds no matter how each half is internally reordered — the index condition only cares about which half each element lives in. So we may sort each half freely and still count left-vs-right pairs correctly. That is the license for divide and conquer:

total = pairs(left half) + pairs(right half) + cross pairs

2Aha

Sorted halves turn cross counting into one forward sweep

With both halves sorted ascending, as the left element x grows, the set of right values with x > 2 * value can only grow with it. So a single pointer j sweeps the right half forward only — it never resets:

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

x = 1 → 1 > 2*1? no                  j stays at 0 → +0
x = 2 → 2 > 2*1? no                  j stays at 0 → +0
x = 3 → 3 > 2*1? yes, 3 > 2*3? no    j moves to 1 → +1

The two pointers together travel the range once, so each combine step is O(n).

3Aha

Count first, merge second — the predicates differ

In Count Inversions you can count during the merge, because the merge comparison and the pair condition are the same test. Here the pair condition is nums[i] > 2 * nums[j] — a different predicate from the merge's nums[i] <= nums[k] — so counting mid-merge silently miscounts. The fix is two clean passes per combine: a counting sweep first, then a standard merge.

Brute force vs optimal

	Brute force	Optimal
Time	O(n²)	O(n log n)
Space	O(1)	O(n)
At n = 5 * 10^4	~1.25 * 10^9 checks — TLE	~8 * 10^5 steps — fast

Full code for both approaches lives in the Approaches selector below.

Summary

Key takeaway

Merge sort is a pair-counting engine: count pairs inside each half recursively, count cross pairs with one forward sweep over the two sorted halves, then merge. Any pair condition that is monotone on sorted values — plain >, more-than-double, a difference in a range — fits the same skeleton.

sortCount(lo, hi):
  if the range has fewer than 2 elements: return 0
  mid = (lo + hi) / 2
  count = sortCount(lo, mid) + sortCount(mid, hi)
  j = mid
  for i in [lo, mid):                      # both halves now sorted
    advance j while nums[i] > 2 * nums[j]
    count += j - mid
  merge the two sorted halves
  return count