.png)
Count Reverse Pairs
Problem Statement
You are given an integer array nums.
A reverse pair is a pair (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 = [1,3,2,3,1]
Output
2
Explanation
(3,1) at indices (1,4)
(3,1) at indices (3,4)
Example 2
Input
nums = [2,4,3,5,1]
Output
3
Why This Problem Is Important
- Very common hard interview problem
- Tests divide and conquer
- Uses merge sort logic
- Checks ability to count pairs efficiently
- Appears in FAANG-level interviews
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force | O(n²) | O(1) |
| Approach 2 | Optimized Brute (Early Break) | O(n²) | O(1) |
| Approach 3 | Merge Sort Based (Optimal) | O(n log n) | O(n) |
Approach 1: Brute Force
Idea
Check every possible pair (i, j) and count if condition satisfies.
Algorithm
- Initialize count = 0
- For each i from 0 to n-1
- For each j from i+1 to n-1
- If nums[i] > 2 * nums[j] → increment count
- Return count
Time & Space Complexity
- Time: O(n²)
- Space: O(1)
C
#include
int main() {
int nums[] = {1,3,2,3,1};
int n = 5, count = 0;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(nums[i] > 2 * nums[j])
count++;
}
}
printf("Input: [1,3,2,3,1]\n");
printf("Output: %d\n", count);
return 0;
}
C++
#include
using namespace std;
int main() {
int nums[] = {1,3,2,3,1};
int n = 5, count = 0;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(nums[i] > 2LL * nums[j])
count++;
}
}
cout << "Input: [1,3,2,3,1]" << endl;
cout << "Output: " << count << endl;
return 0;
}
Java
public class ReversePairsBrute {
public static void main(String[] args) {
int[] nums = {1,3,2,3,1};
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++;
}
}
System.out.println("Input: [1,3,2,3,1]");
System.out.println("Output: " + count);
}
}
Python
nums = [1,3,2,3,1]
count = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] > 2 * nums[j]:
count += 1
print("Input: [1,3,2,3,1]")
print("Output:", count)
JavaScript
let nums = [1,3,2,3,1];
let count = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] > 2 * nums[j])
count++;
}
}
console.log("Input: [1,3,2,3,1]");
console.log("Output:", count);
C#
using System;
class ReversePairsBrute {
static void Main() {
int[] nums = {1,3,2,3,1};
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++;
}
}
Console.WriteLine("Input: [1,3,2,3,1]");
Console.WriteLine("Output: " + count);
}
}
Final Output
Input: [1,3,2,3,1]
Output: 2
Approach 2: Optimized Brute Force
Idea
Sort the array and break early when condition fails.
Algorithm
- Sort array
- For each i
- For j > i, stop checking once nums[i] <= 2 * nums[j]
Time & Space Complexity
- Time: O(n²) worst case
- Space: O(1)
C
#include
void sort(int arr[], int n){
for(int i=0;i arr[j+1]){
int t = arr[j];
arr[j] = arr[j+1];
arr[j+1] = t;
}
}
}
}
int main() {
int nums[] = {1,3,2,3,1};
int n = 5, count = 0;
sort(nums, n);
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(nums[i] > 2 * nums[j])
count++;
else
break;
}
}
printf("Sorted Input: [1,1,2,3,3]\n");
printf("Output: %d\n", count);
return 0;
}
C++
#include
#include
using namespace std;
int main() {
int nums[] = {1,3,2,3,1};
int n = 5, count = 0;
sort(nums, nums + n);
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(nums[i] > 2LL * nums[j])
count++;
else
break;
}
}
cout << "Sorted Input: [1,1,2,3,3]" << endl;
cout << "Output: " << count << endl;
return 0;
}
Java
import java.util.Arrays;
public class ReversePairsOptimized {
public static void main(String[] args) {
int[] nums = {1,3,2,3,1};
int count = 0;
Arrays.sort(nums);
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++;
else
break;
}
}
System.out.println("Sorted Input: [1,1,2,3,3]");
System.out.println("Output: " + count);
}
}
Python
nums = [1,3,2,3,1]
nums.sort()
count = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] > 2 * nums[j]:
count += 1
else:
break
print("Sorted Input:", nums)
print("Output:", count)
JavaScript
let nums = [1,3,2,3,1];
nums.sort((a,b) => a-b);
let count = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] > 2 * nums[j])
count++;
else
break;
}
}
console.log("Sorted Input:", nums);
console.log("Output:", count);
C#
using System;
class ReversePairsOptimized {
static void Main() {
int[] nums = {1,3,2,3,1};
Array.Sort(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++;
else
break;
}
}
Console.WriteLine("Sorted Input: [1,1,2,3,3]");
Console.WriteLine("Output: " + count);
}
}
Final Output
Sorted Input: [1,1,2,3,3]
Output: 2
Limitation
Still fails for large inputs.
Used only to show thinking improvement, not accepted in interviews.
Approach 3: Merge Sort Based (Optimal)
Core Idea
- Split array into two halves
- Count reverse pairs before merging
- Both halves are sorted, enabling two-pointer counting
Key Observation
If left half and right half are sorted:
nums[i] > 2 * nums[j]
can be counted efficiently using pointers.
Algorithm
- Perform merge sort
- Before merging:
- For each element in left half
- Move pointer in right half
- Count valid reverse pairs
- Merge the halves
- Return total count
Time & Space Complexity
- Time: O(n log n)
- Space: O(n)
C++
#include
#include
using namespace std;
int mergeSort(vector& nums, int low, int high) {
if (low >= high) return 0;
int mid = (low + high) / 2;
int count = mergeSort(nums, low, mid)
+ mergeSort(nums, mid + 1, high);
int j = mid + 1;
for (int i = low; i <= mid; i++) {
while (j <= high && (long long)nums[i] > 2LL * nums[j])
j++;
count += j - (mid + 1);
}
vector temp;
int left = low, right = mid + 1;
while (left <= mid && right <= high)
temp.push_back(nums[left] <= nums[right] ? nums[left++] : nums[right++]);
while (left <= mid) temp.push_back(nums[left++]);
while (right <= high) temp.push_back(nums[right++]);
for (int i = low; i <= high; i++)
nums[i] = temp[i - low];
return count;
}
int main() {
vector nums = {1,3,2,3,1};
int result = mergeSort(nums, 0, nums.size() - 1);
cout << "Input: [1,3,2,3,1]" << endl;
cout << "Output: " << result << endl;
return 0;
}
Java
public class ReversePairsOptimal {
static int mergeSort(int[] nums, int low, int high) {
if (low >= high) return 0;
int mid = (low + high) / 2;
int count = mergeSort(nums, low, mid)
+ mergeSort(nums, mid + 1, high);
int j = mid + 1;
for (int i = low; i <= mid; i++) {
while (j <= high && (long)nums[i] > 2L * nums[j])
j++;
count += j - (mid + 1);
}
int[] temp = new int[high - low + 1];
int left = low, right = mid + 1, k = 0;
while (left <= mid && right <= high)
temp[k++] = nums[left] <= nums[right] ? nums[left++] : nums[right++];
while (left <= mid) temp[k++] = nums[left++];
while (right <= high) temp[k++] = nums[right++];
System.arraycopy(temp, 0, nums, low, temp.length);
return count;
}
public static void main(String[] args) {
int[] nums = {1,3,2,3,1};
int result = mergeSort(nums, 0, nums.length - 1);
System.out.println("Input: [1,3,2,3,1]");
System.out.println("Output: " + result);
}
}
Python
def merge_sort(nums):
if len(nums) <= 1:
return nums, 0
mid = len(nums) // 2
left, c1 = merge_sort(nums[:mid])
right, c2 = merge_sort(nums[mid:])
count = c1 + c2
j = 0
for i in range(len(left)):
while j < len(right) and left[i] > 2 * right[j]:
j += 1
count += j
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged, count
nums = [1,3,2,3,1]
_, result = merge_sort(nums)
print("Input: [1,3,2,3,1]")
print("Output:", result)
JavaScript
function mergeSort(nums) {
if (nums.length <= 1) return [nums, 0];
let mid = Math.floor(nums.length / 2);
let [left, c1] = mergeSort(nums.slice(0, mid));
let [right, c2] = mergeSort(nums.slice(mid));
let count = c1 + c2;
let j = 0;
for (let i = 0; i < left.length; i++) {
while (j < right.length && left[i] > 2 * right[j])
j++;
count += j;
}
let merged = [], i = 0;
j = 0;
while (i < left.length && j < right.length)
merged.push(left[i] <= right[j] ? left[i++] : right[j++]);
return [merged.concat(left.slice(i)).concat(right.slice(j)), count];
}
let nums = [1,3,2,3,1];
let result = mergeSort(nums)[1];
console.log("Input: [1,3,2,3,1]");
console.log("Output:", result);
C#
using System;
class ReversePairsOptimal {
static int MergeSort(int[] nums, int low, int high) {
if (low >= high) return 0;
int mid = (low + high) / 2;
int count = MergeSort(nums, low, mid)
+ MergeSort(nums, mid + 1, high);
int j = mid + 1;
for (int i = low; i <= mid; i++) {
while (j <= high && (long)nums[i] > 2L * nums[j])
j++;
count += j - (mid + 1);
}
int[] temp = new int[high - low + 1];
int left = low, right = mid + 1, k = 0;
while (left <= mid && right <= high)
temp[k++] = nums[left] <= nums[right] ? nums[left++] : nums[right++];
while (left <= mid) temp[k++] = nums[left++];
while (right <= high) temp[k++] = nums[right++];
for (int i = low; i <= high; i++)
nums[i] = temp[i - low];
return count;
}
static void Main() {
int[] nums = {1,3,2,3,1};
int result = MergeSort(nums, 0, nums.Length - 1);
Console.WriteLine("Input: [1,3,2,3,1]");
Console.WriteLine("Output: " + result);
}
}
Final Output
Input: [1,3,2,3,1]
Output: 2
Summary
- Brute force is easy but slow
- Optimized brute still fails for large inputs
- Merge sort approach is the only accepted optimal solution
- Counting is done before merging, not after
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
