Reverse Pairs (LeetCode 493) Explained | Optimal Merge Sort Solution with C++

Problem Statement

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

A reverse pair is a pair of indices (i, j) such that:

• 0 <= i < j < nums.length
• nums[i] > 2 * nums[j]

Your task is to count all such reverse pairs efficiently.

Example 1

Input

nums = [1,3,2,3,1]

Output

2

Explanation

The reverse pairs are:

(3,1) → 3 > 2 × 1

(3,1) → 3 > 2 × 1

Therefore, the total number of reverse pairs is 2.

Example 2

Input

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

Output

3

Explanation

The reverse pairs are:

(4,1) → 4 > 2 × 1

(3,1) → 3 > 2 × 1

(5,1) → 5 > 2 × 1

Hence, the answer is 3.

Naive (Brute Force) Solution

The simplest approach is to check every possible pair (i, j) where i < j.

If:

nums[i] > 2 * nums[j]

then it is a reverse pair, so increment the count.

C++ Code

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        int count = 0;
        int n = nums.size();

        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                if((long long)nums[i] > 2LL * nums[j]) {
                    count++;
                }
            }
        }

        return count;
    }
};

Dry Run

nums = [1,3,2,3,1]

Complexity Analysis

• Time Complexity: O(n²)
• Space Complexity: O(1)

Why It Gets TLE

For:

n = 50,000

the number of comparisons is approximately:

n² = 50,000 × 50,000 = 2.5 billion

which is too slow.

That's why we use the Merge Sort based O(n log n) solution.

Optimal Approach (Merge Sort)

prerequisite:

merge sort

The brute-force solution checks every pair, resulting in O(n²) time.

To optimize, we use Merge Sort.

Key Observation

During Merge Sort, the left half and right half are already sorted.

Suppose:

Left = [1, 4, 5]

Right = [1, 2]

For each element in the left half, we want to count how many elements in the right half satisfy:

arr[i] > 2LL * arr[j]

Since the right half is sorted, once a j satisfies the condition, all previous valid j's are also counted. We can use a moving pointer and count efficiently.

Dry Run:

Algorithm

1. Divide the array into two halves.
2. Recursively count reverse pairs in the left half.
3. Recursively count reverse pairs in the right half.
4. Count reverse pairs across the two halves.
5. Merge the two sorted halves.

class Solution {
public:
    int merge(vector<int>& arr, int low, int mid, int high) {
        vector<int> temp;
        int left = low;
        int right = mid + 1;

        while(left <= mid && right <= high) {
            if(arr[left] <= arr[right]) {
                temp.push_back(arr[left++]);
            } else {
                temp.push_back(arr[right++]);
            }
        }

        while(left <= mid) temp.push_back(arr[left++]);
        while(right <= high) temp.push_back(arr[right++]);

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

        return 0;
    }

    int countPairs(vector<int>& arr, int low, int mid, int high) {
        int right = mid + 1;
        int count = 0;

        for(int i = low; i <= mid; i++) {
            while(right <= high &&
                  arr[i] > 2LL * arr[right]) {
                right++;
            }

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

        return count;
    }

    int mergeSort(vector<int>& arr, int low, int high) {
        if(low >= high) return 0;

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

        int count = 0;

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

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

        merge(arr, low, mid, high);

        return count;
    }

    int reversePairs(vector<int>& nums) {
        return mergeSort(nums, 0, nums.size() - 1);
    }
};

Complexity

• Time Complexity: O(n log n)
• Space Complexity: O(n)

problem link:

Reverse Pairs - LeetCode

video reference link:

Reverse Pairs | Hard Interview Question