Command Palette

Search for a command to run...

Hectal
Problem 36.3 · Advanced Data StructuresHard

Reverse Pairs

PatternRange Queries (Fenwick & Segment Trees)Divide and Conquer

What it teaches: Merge sort counting with a different comparison (nums[i] > 2 × nums[j]) before merging.

Practise it on judges as “Reverse Pairs”.

In plain words

Count pairs where an earlier number is more than double a later one. Merge sort helps: once both halves are sorted, one pointer can walk through the right half for every left number, counting how many right numbers are small enough. Then merge as usual.

Return the number of such pairs. Example: nums = [1, 3, 2, 3, 1] → 2.

The problem

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

Example 1

Input: nums = [1, 3, 2, 3, 1]
Output: 2

Constraints

  • 1 ≤ n ≤ 5 × 10⁴
  • Values fit in int (2 × value may not)

Pattern clues in the wording

  • → Pair counting with an order condition

These clues point to Range Queries (Fenwick & Segment Trees): Answer sums, minimums or counts over any range while the array keeps changing, in O(log n) per query and update.

Stuck? Take one hint at a time

Solution · starter
class Solution {
    public int reversePairs(int[] nums) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#InputExpected
1
nums = [1,3,2,3,1]
2
2
nums = [2,4,3,5,1]
3

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Merge sort + two pointers · O(n log n)
1

Merge sort + two pointers

Time O(n log n) Space O(n)

For each i in the left half, advance j in the right half while nums[i] > 2 × nums[j]; add (j − mid − 1). Then merge normally.

▶ Dry run: Count across halves, then mergenums = [1, 3, 2, 3, 1]
1
0
3
1
2
2
3
3
1
4

Step 1/4Split into [1, 3, 2] and [3, 1].

Approach 1
class Solution {
    public int reversePairs(int[] nums) {
        return sort(nums, new int[nums.length], 0, nums.length - 1);
    }

    private int sort(int[] a, int[] tmp, int lo, int hi) {
        if (lo >= hi) return 0;
        int mid = (lo + hi) >>> 1;
        int count = sort(a, tmp, lo, mid) + sort(a, tmp, mid + 1, hi);
        for (int i = lo, j = mid + 1; i <= mid; i++) {
            while (j <= hi && (long) a[i] > 2L * a[j]) j++;
            count += j - mid - 1;
        }
        int i = lo, j = mid + 1, k = lo;
        while (i <= mid || j <= hi) tmp[k++] = (j > hi || (i <= mid && a[i] <= a[j])) ? a[i++] : a[j++];
        System.arraycopy(tmp, lo, a, lo, hi - lo + 1);
        return count;
    }
}

Verdict: Counting and merging are separate passes.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Negative numbers
  • Large values (overflow)

Mistakes people make

  • Computing 2 × nums[j] in int.

Interview

Follow-up questions

How would a Fenwick tree solve it?