Reverse Pairs — Editorial

Opening the reading…

Intuitionwhy sorting exposes the pairs without checking them one by one

A reverse pair has its first index in the left part of an interval and its second index in the right part. If you split the array in half, pairs fall into three groups: pairs entirely in the left half, pairs entirely in the right half, and cross pairs with one element in each half. The first two groups can be counted recursively, so the real work is counting the cross pairs.

After the recursive calls, both halves are sorted. For each value in the left half, scan the right half until nums[i] is no longer greater than 2 * nums[j]. Because the left values are sorted, the stopping position never moves backward: a larger left value can only keep the pointer where it is or move it farther right. Count the accepted right-side values, then merge the halves so the parent interval receives the sorted order it needs.

The monotone pointer counts a prefix of the sorted right half.

Approachcount cross pairs before merging the two sorted halves

Split the current interval at its midpoint and recursively count reverse pairs in both halves, because every pair that stays inside one half belongs to one of those recursive subproblems.

Set j to the beginning of the right half and scan each i in the left half, because the two halves are sorted and a single forward pointer can retain all progress from earlier left values.

While nums[i] > 2 * nums[j], advance j, because every right-half value before j is a valid partner for this left value and every later value is not.

Add j - (mid + 1) to the answer for each left value, because that is exactly the number of right-half indices reached by j and therefore satisfying the inequality.

Merge the two sorted halves after counting, because the parent call relies on the entire interval being sorted when it counts its own cross pairs.

Return the sum of the left count, right count, and cross count, with the base case left >= right returning zero because an interval with fewer than two elements contains no pair.

Complexitythe merge work dominates each recursion level

MEASURE	BOUND	WHY
Time	O(n log n)	At every recursion level, each element participates in one forward counting scan and one merge, so that level costs O(n). The midpoint split creates O(log n) levels, and no element is rescanned across unrelated intervals.
Space	O(n) extra	The temporary merge array uses O(n) space at the widest level, while the balanced recursion stack uses O(log n); these are not simultaneously larger than O(n). The returned count is a scalar and there is no output array. The bound stays O(n) for every input shape because the split is by index, not by the values in the input.

Here n is the length of nums. The recursion always splits by midpoint, so its depth is O(log n).

Annotated solutionC++ · recursive merge sort with a monotone cross-pair scan

CPPCount recursive pairs, scan cross pairs with one pointer, then merge the interval.

#include <vector>
using namespace std;

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

private:
    int mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        int count = mergeSort(nums, left, mid);
        count += mergeSort(nums, mid + 1, right);

        int j = mid + 1;
        for (int i = left; i <= mid; ++i) {
            while (j <= right &&
                   static_cast<long long>(nums[i]) > 2LL * nums[j]) {
                ++j;
            }
            count += j - (mid + 1);
        }

        merge(nums, left, mid, right);
        return count;
    }

    void merge(vector<int>& nums, int left, int mid, int right) {
        vector<int> temp;
        temp.reserve(right - left + 1);

        int i = left;
        int j = mid + 1;

        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp.push_back(nums[i++]);
            } else {
                temp.push_back(nums[j++]);
            }
        }

        while (i <= mid) {
            temp.push_back(nums[i++]);
        }
        while (j <= right) {
            temp.push_back(nums[j++]);
        }

        for (int p = 0; p < static_cast<int>(temp.size()); ++p) {
            nums[left + p] = temp[p];
        }
    }
};

The cast in the comparison is essential, not cosmetic. nums[i] and nums[j] are int values, and 2 * nums[j] can overflow before the comparison if the multiplication is performed as int. Converting nums[i] to long long and writing 2LL makes the whole comparison use 64-bit arithmetic, including values near both ends of the allowed integer range.