AlgoViz
HomeArrays & Hashing

Reverse Pairs

Hard

A separate counting pass inside merge sort

Problem

Given an integer array nums. Return the number of reverse pairs in the array. An index pair (i, j) is called a reverse pair if: 0 <= i < j < nums.length nums[i] > 2 * nums[j]

In simple words

Count pairs where the earlier number is more than double the later one, using merge sort.

The idea

The condition nums[i] > 2 * nums[j] does not line up with the merge comparison, so count reverse pairs in a dedicated two-pointer sweep over the two sorted halves before merging them. Both halves being sorted is what keeps that sweep linear.

The trick

  • Count first with its own two-pointer pass, then merge — combining them is wrong.
  • Use 64-bit arithmetic; 2 * nums[j] can overflow.
  • O(n log n) overall.
1
3
2
3
1
0
1
2
3
4

Step 1 of 12. Brute force: check every pair where nums[i] > 2·nums[j]. Values: 1, 3, 2, 3, 1.

1/12
Brute force
timeO(n²)spaceO(1)

Every pair.

1for (let i = 0; i < n; i++)2  for (let j = i + 1; j < n; j++)3    if (nums[i] > 2 * nums[j]) count++;4return count;

Input

array
[1, 3, 2, 3, 1]

Memory

i
—
j
—

Output

count
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 3, 2, 3, 1]
Output:
2
Explanation:
Pairs where a[i] > 2*a[j] with i<j: there are 2.

Example 2

Input:
nums = [2, 4, 3, 5, 1]
Output:
3
Explanation:
3 such important reverse pairs.

Example 3

Input:
nums = [1, 2, 3]
Output:
0
Explanation:
None qualify → 0.

Constraints

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

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.