Reverse Pairs | devLap

Given an integer array nums, return the number of reverse pairs.

A reverse pair is defined as:

i < j && nums[i] > 2 * nums[j]

Brute Force Approach

Intuition

Generate every possible pair (i, j) where i < j and check whether:

nums[i] > 2 * nums[j]

If the condition is true, increment the count.

Java

class Solution {
    public int reversePairs(int[] nums) {

        int count = 0;

        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {

                if ((long) nums[i] > 2L * nums[j]) {
                    count++;
                }
            }
        }

        return count;
    }
}

Complexity

Time: O(N²)
Space: O(1)

Why Think About Merge Sort?

The brute force solution checks every pair individually.

Can we count multiple valid pairs together?

The answer is yes, if the array is sorted.

Merge Sort naturally divides the array into sorted halves, which helps us efficiently count reverse pairs during the merge step.

Key Observation

Suppose after recursion we have:

Left  = [3, 5]
Right = [1, 2]

Both halves are already sorted.

We need to count:

left[i] > 2 * right[j]

For every element in the left half.

The Magic of Sorting

Consider:

5 > 2 * 1   ✔
5 > 2 * 2   ✔

Since the right half is sorted:

[1, 2]

once a value satisfies the condition, all smaller values before it will also satisfy it.

This allows us to use a moving pointer and count multiple pairs at once instead of checking every combination.

Dry Run

Left  = [3, 5]
Right = [1, 2]

Start:

j = 0

For 3

3 > 2 * 1
3 > 2

Valid.

Move j.

3 > 2 * 2
3 > 4

False.

Pairs contributed:

For 5

Continue from current j.

5 > 2 * 2
5 > 4

Valid.

Move j.

Pairs contributed:

Total reverse pairs:

Which are:

(3,1)
(5,1)
(5,2)

Merge Sort Strategy

For every merge step:

Count pairs in left half
+
Count pairs in right half
+
Count cross pairs

The important detail:

Count first
Then merge

Because counting requires two separate sorted halves.

Once merged, that boundary disappears.

Optimal Solution

Intuition

While merging two sorted halves:

Use a pointer on the right half.
For every element in the left half, count how many elements satisfy:

nums[i] > 2 * nums[j]

Since both halves are sorted, the pointer never moves backward.

This allows counting all cross pairs in linear time.

Java

class Solution {

    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }

    private int mergeSort(int[] nums, int low, int high) {

        if (low >= high) return 0;

        int mid = low + (high - low) / 2;

        int count = 0;

        count += mergeSort(nums, low, mid);
        count += mergeSort(nums, mid + 1, high);

        count += countPairs(nums, low, mid, high);

        merge(nums, low, mid, high);

        return count;
    }

    private int countPairs(int[] nums, int low, int mid, int high) {

        int count = 0;
        int right = mid + 1;

        for (int i = low; i <= mid; i++) {

            while (right <= high &&
                   (long) nums[i] > 2L * nums[right]) {
                right++;
            }

            count += right - (mid + 1);
        }

        return count;
    }

    private void merge(int[] nums, int low, int mid, int high) {

        List<Integer> temp = new ArrayList<>();

        int left = low;
        int right = mid + 1;

        while (left <= mid && right <= high) {

            if (nums[left] <= nums[right]) {
                temp.add(nums[left++]);
            } else {
                temp.add(nums[right++]);
            }
        }

        while (left <= mid) {
            temp.add(nums[left++]);
        }

        while (right <= high) {
            temp.add(nums[right++]);
        }

        for (int i = low; i <= high; i++) {
            nums[i] = temp.get(i - low);
        }
    }
}

Complexity

Time: O(N log N)
Space: O(N)

Takeaway

Whenever a problem asks you to count pairs:

i < j

and the condition involves comparing elements from two positions, ask yourself:

Can sorting help me count multiple pairs together?

If the answer is yes, Merge Sort is often the hidden optimization.

Reverse Pairs is a classic example where sorting transforms an O(N²) brute force solution into an O(N log N) solution.