Reverse pairs

Brute Force Approach#

Check every pair (i, j) with i < j and count pairs where nums[i] > 2 * nums[j]. Straightforward but O(n²) — too slow for large inputs.

class Solution {
public:
    int reversePairs(vector<int>& nums) {

        int counter=0;
        for(int i=0;i<nums.size();i++){
            for(int j=i+1;j<nums.size();j++)
            {
                if(nums[i] > 2*nums[j]){
                    counter++;
                }
            }
        }
        return counter;
    }
};

Better Approach#

Use a modified merge sort. During the merge step, before merging two sorted halves [lo, mid] and [mid+1, hi], count the reverse pairs: for each element in the left half use a two-pointer to count how many elements in the right half satisfy left > 2 * right. Because both halves are already sorted, the two-pointer moves monotonically and counts in O(n) per merge level. Combined with the O(n log n) merge sort overhead, the total complexity is O(n log n).