Given an integer array nums of length n. A reverse pair is a pair of indices (i, j) such that i < j and nums[i] > 2 * nums[j]. Return the total number of reverse pairs in the array.
Example 1
Input: nums = [10, 5, 2, 6, 1, 8, 3, -2]
Output: 14
Explanation: Some valid reverse pairs are (10, 2), (10, 1), (5, 2), (6, 1), (8, 3), and every earlier value paired with -2. Counting all valid pairs gives 14.
Example 2
Input: nums = [-5, -5, -3, -2]
Output: 4
Explanation: Negative values still follow the same strict condition. The valid pairs are (-5, -5), (-5, -3), the second (-5, -3), and (-3, -2).
Brute Force Approach
Each index is treated as the left side of a possible pair, and every later index is compared against it. Whenever the left value is more than twice the later value, the answer increases by one.
Algorithm
Initialize the reverse-pair count as
0; arrays with fewer than two values cannot form a pair.Treat each position from the first index to the second-last index as the left side of a possible pair.
Compare the chosen left value with every value placed after it.
Increase the count when the left value is strictly greater than twice the right value, using widened arithmetic where needed.
Continue until every ordered pair with the left index before the right index has been tested.
Return the final count.
Dry Run
Reverse Pair fixed
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the number of reverse pairs. int reversePairs(vector<int>& nums) { int n = nums.size(); int pairs = 0; // Choose each position as the left side of a possible pair. for (int left = 0; left < n; left++) { long long leftValue = nums[left]; // Check only positions that appear after the left index. for (int right = left + 1; right < n; right++) { long long doubledRight = 2LL * nums[right]; // A reverse pair needs the left value to be more than twice the right value. if (leftValue > doubledRight) { pairs++; } } } return pairs; }};// Driver codeint main() { vector<int> nums = {10, 5, 2, 6, 1, 8, 3, -2}; // instance for class Solution Solution sol; cout << sol.reversePairs(nums) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n²), because every ordered pair of indices may be checked once.
Space Complexity: O(1), because only a fixed number of counters is used.
Optimal Approach
The merge sort technique improves the direct method by using sorted halves. After the left half and right half are sorted, all valid cross pairs can be counted with a moving pointer before the halves are merged.
For a fixed value in the left half, every right-half value before the pointer already satisfies the reverse-pair condition. The pointer never needs to move backward because the left half is processed in sorted order. This avoids repeated pair-by-pair comparisons while preserving the original left-before-right relationship created by the recursive split.
Algorithm
Copy the input array and recursively divide it until each range has at most one value; such a range contributes
0pairs.Count reverse pairs inside the left half and inside the right half.
Before merging, use the two sorted halves to count cross pairs where the left index belongs to the left half and the right index belongs to the right half.
For each left-half value, advance the right pointer while the value is greater than twice the right-half value, then add the number of crossed right-half values.
Merge the two sorted halves so the parent range can perform the same counting step.
Return the sum of left-half pairs, right-half pairs, and cross pairs after the full range has been processed.
Dry Run
Reverse Pair - Merge sort
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Counts reverse pairs while sorting the selected range. int mergeSort(vector<int>& arr, int left, int right) { // A range with zero or one value cannot contain a pair. if (left >= right) { return 0; } int mid = left + (right - left) / 2; int pairs = 0; pairs += mergeSort(arr, left, mid); pairs += mergeSort(arr, mid + 1, right); pairs += countCrossPairs(arr, left, mid, right); mergeSortedHalves(arr, left, mid, right); return pairs; } // Returns cross pairs from the left half to the right half. int countCrossPairs(vector<int>& arr, int left, int mid, int right) { int pairs = 0; int rightPointer = mid + 1; // Count how many right-half values are valid for each left-half value. for (int leftPointer = left; leftPointer <= mid; leftPointer++) { long long leftValue = arr[leftPointer]; // Move across right-half values that satisfy the reverse-pair condition. while (rightPointer <= right && leftValue > 2LL * arr[rightPointer]) { rightPointer++; } pairs += rightPointer - (mid + 1); } return pairs; } // Merges two sorted halves into one sorted range. void mergeSortedHalves(vector<int>& arr, int left, int mid, int right) { vector<int> merged; int first = left; int second = mid + 1; // Merge the smaller available value from the two halves. while (first <= mid && second <= right) { // The smaller value should be placed next in the merged range. if (arr[first] <= arr[second]) { merged.push_back(arr[first]); first++; } else { merged.push_back(arr[second]); second++; } } // Copy any remaining values from the left half. while (first <= mid) { merged.push_back(arr[first]); first++; } // Copy any remaining values from the right half. while (second <= right) { merged.push_back(arr[second]); second++; } // Write the merged values back into the selected range. for (int index = 0; index < merged.size(); index++) { arr[left + index] = merged[index]; } }public: // Returns the number of reverse pairs. int reversePairs(vector<int>& nums) { vector<int> arr = nums; int n = arr.size(); // Arrays with fewer than two values cannot form a pair. if (n < 2) { return 0; } return mergeSort(arr, 0, n - 1); }};// Driver codeint main() { vector<int> nums = {10, 5, 2, 6, 1, 8, 3, -2}; // instance for class Solution Solution sol; cout << sol.reversePairs(nums) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n log n), because each merge-sort level processes the array once and there are O(log n) levels.
Space Complexity: O(n), because the copied array and temporary merge storage use linear extra space.
Interview follow-up Questions
Before merging, the left and right halves are already sorted but still represent their original left-before-right split. That is the exact moment when cross pairs can be counted efficiently without losing the index-order relationship.
Be the first to add a comment.