Reverse Pairs solution and explanation
Google
Deloitte
9 more videos on this problem
Reverse Pairs | Hard Interview Questiontake U forward · 32:26 · 393K views
Reverse Pairs | Leetcode(HARD) | Please watch new video - link in descriptiontake U forward · 19:34 · 180K views
Reverse Pairs Problem Solved | Master Merge Sort Approach for Coding InterviewsHustlerCoder · 34:06 · 7K views
LeetCode 493. Reverse Pairs Explanation and Solutionhappygirlzt · 11:27 · 6K views
493. Reverse Pairs (Leetcode Hard)Programming Live with Larry · 20:04 · 2K views
Reverse Pairs - LeetCode (Hard) | Merge Sort | O(NlogN) Most Optimal ApproachThe Lame Coder · 40:05 · 1K views
LeetCode 493 🔥 Reverse Pairs | SDE Interview Sheet | Optimal Merge Sort + Dry Run Study Placement · 2:11 · 1K views
493. Reverse Pairs | LeetCode | Inversion Count | Merge Sort | Divide & Conquer | RecursionCoding Gist · 12:01 · 1K views
Reverse Pairs - Modified Merge Sort | Java | C++ | Brute-Optimal - Explain | leetCode #493 - HardCodeXam · 43:32 · 1K views
LeetCode 493 | Reverse Pairs | Explained with Merge Sort | MAANG Prep | Pen Paper PreparationPen And Paper · 12:43 · 781 views
The problem
Given an integer array nums, return the number of reverse pairs in the array.
A reverse pair is a pair (i, j) where:
0 <= i < j < nums.lengthandnums[i] > 2 * nums[j].
Example 1:
Input: nums = [1,3,2,3,1] Output: 2 Explanation: The reverse pairs are: (1, 4) --> nums[1] = 3, nums[4] = 1, 3 > 2 * 1 (3, 4) --> nums[3] = 3, nums[4] = 1, 3 > 2 * 1
Example 2:
Input: nums = [2,4,3,5,1] Output: 3 Explanation: The reverse pairs are: (1, 4) --> nums[1] = 4, nums[4] = 1, 4 > 2 * 1 (2, 4) --> nums[2] = 3, nums[4] = 1, 3 > 2 * 1 (3, 4) --> nums[3] = 5, nums[4] = 1, 5 > 2 * 1
Constraints:
1 <= nums.length <= 5 * 104-231 <= nums[i] <= 231 - 1
Approach overview
Problem Overview: Given an integer array nums, count pairs (i, j) such that i < j and nums[i] > 2 * nums[j]. The challenge is detecting these pairs efficiently without checking every combination.
Approach 1: Naive Brute Force (O(n2) time, O(1) space)
The straightforward solution checks every pair of indices. Use two nested loops: fix i, then iterate j from i + 1 to the end of the array. For each pair, test the condition nums[i] > 2 * nums[j] and increment a counter when it holds. This approach requires no additional data structures and is easy to implement in any language. However, the nested iteration results in quadratic time, which becomes too slow when the array size grows into tens of thousands. The brute force version mainly helps validate correctness or build intuition before implementing an optimized algorithm.
Approach 2: Optimized Merge Sort (O(n log n) time, O(n) space)
The optimal solution uses a modified merge sort with a divide and conquer strategy. While splitting the array into halves and sorting them, you also count valid reverse pairs across the two halves. Because each half is already sorted, you can efficiently detect pairs using a two-pointer scan before merging. For each element in the left half, advance a pointer in the right half while nums[i] > 2 * nums[j]. The number of valid indices skipped contributes to the reverse pair count.
After counting cross-half pairs, perform the standard merge step to combine the two sorted halves. Sorting during recursion guarantees that each level can count pairs in linear time. Since merge sort has log n levels and each level processes n elements, the overall complexity becomes O(n log n). This technique is closely related to counting inversions in arrays and frequently appears in problems involving ordered relationships.
Although other advanced solutions exist using a Binary Indexed Tree, segment tree, or ordered set, the merge sort approach is typically preferred because it is easier to implement and performs reliably across languages without requiring coordinate compression or additional indexing tricks.
Recommended for interviews: The optimized merge sort solution is the expected answer in most interviews. It demonstrates your understanding of divide-and-conquer counting techniques and how sorted subarrays enable faster pair detection. Starting with the brute force explanation shows clear reasoning, but implementing the O(n log n) merge sort solution proves you can optimize beyond quadratic scans.
Approach 1: Naive Brute Force Approach
The simplest way to solve the problem is by checking each possible pair in the array and counting those that fit the reverse pair condition, nums[i] > 2 * nums[j].
This approach involves nested loops where the first loop picks a number and the second loop checks all numbers coming after it.
def reversePairs(nums):
count = 0
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] > 2 * nums[j]:
count += 1
return countpublic class Solution {
public int reversePairs(int[] 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] > 2 * (long)nums[j]) {
count++;
}
}
}
return count;
}
}#include <vector>
int reversePairs(std::vector<int>& nums) {
int count = 0;
for (int i = 0; i < nums.size(); i++) {
for (int j = i + 1; j < nums.size(); j++) {
if ((long)nums[i] > 2 * (long)nums[j]) {
count++;
}
}
}
return count;
}function reversePairs(nums) {
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++;
}
}
}
return count;
}#include <stdio.h>
int reversePairs(int* nums, int numsSize) {
int count = 0;
for (int i = 0; i < numsSize; i++) {
for (int j = i + 1; j < numsSize; j++) {
if ((long)nums[i] > 2 * (long)nums[j]) {
count++;
}
}
}
return count;
}public class Solution {
public int ReversePairs(int[] 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] > 2 * (long)nums[j]) {
count++;
}
}
}
return count;
}
}This Python implementation uses nested loops to determine all reverse pairs, where the condition is met.
Time Complexity: O(n^2).
Space Complexity: O(1).
Approach 2: Optimized Merge Sort Approach
To count reverse pairs more efficiently, use a modified merge sort algorithm.
The key is to sort the array while counting the reverse pairs as the elements are merged. As the merge sort combines two sorted subarrays, it's easier to count the number of elements that satisfy the reverse pair condition in a divide and conquer manner.
During the merge step, while comparing an element from the left array with one from the right array, if nums[i] > 2 * nums[j], every element after nums[j] in the right array will satisfy the condition with nums[i]. Hence, increment the counter for such conditions.
def mergeSort(nums, temp, left, right):
if left >= right:
return 0
mid = (left + right) // 2
count = mergeSort(nums, temp, left, mid) + mergeSort(nums, temp, mid + 1, right)
j = mid + 1
for i in range(left, mid + 1):
while j <= right and nums[i] > 2 * nums[j]:
j += 1
count += j - (mid + 1)
nums[left:right+1] = sorted(nums[left:right+1])
return count
def reversePairs(nums):
return mergeSort(nums, [0] * len(nums), 0, len(nums) - 1)public class Solution {
public int reversePairs(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int[] temp = new int[nums.length];
return mergeSort(nums, temp, 0, nums.length - 1);
}
private int mergeSort(int[] nums, int[] temp, int left, int right) {
if (left >= right) return 0;
int mid = left + (right - left) / 2;
int count = mergeSort(nums, temp, left, mid) + mergeSort(nums, temp, mid + 1, right);
count += merge(nums, temp, left, mid, right);
return count;
}
private int merge(int[] nums, int[] temp, int left, int mid, int right) {
int i = left, j = mid + 1, k = left, count = 0;
while (i <= mid) {
while (j <= right && (long)nums[i] > 2 * (long)nums[j]) j++;
count += j - (mid + 1);
i++;
}
System.arraycopy(nums, left, temp, left, right - left + 1);
i = left;
j = mid + 1;
k = left;
while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) {
nums[k++] = temp[i++];
} else {
nums[k++] = temp[j++];
}
}
while (i <= mid) nums[k++] = temp[i++];
while (j <= right) nums[k++] = temp[j++];
return count;
}
}#include <vector>
int merge(std::vector<int>& nums, std::vector<int>& temp, int left, int mid, int right) {
int i = left, j = mid, k = left, count = 0;
while (i <= mid - 1 && j <= right) {
if ((long)nums[i] > 2 * (long)nums[j]) {
count += mid - i;
j++;
} else {
i++;
}
}
i = left;
j = mid;
while (i <= mid - 1 && j <= right) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
while (i <= mid - 1) temp[k++] = nums[i++];
while (j <= right) temp[k++] = nums[j++];
for (i = left; i <= right; i++) nums[i] = temp[i];
return count;
}
int mergeSort(std::vector<int>& nums, std::vector<int>& temp, int left, int right) {
int mid, count = 0;
if (right > left) {
mid = (right + left) / 2;
count += mergeSort(nums, temp, left, mid);
count += mergeSort(nums, temp, mid + 1, right);
count += merge(nums, temp, left, mid + 1, right);
}
return count;
}
int reversePairs(std::vector<int>& nums) {
std::vector<int> temp(nums.size());
return mergeSort(nums, temp, 0, nums.size() - 1);
}function reversePairs(nums) {
if (!nums || nums.length === 0) return 0;
function mergeSort(nums, temp, left, right) {
if (left >= right) return 0;
const mid = Math.floor((left + right) / 2);
let count = mergeSort(nums, temp, left, mid) + mergeSort(nums, temp, mid + 1, right);
let j = mid + 1;
for (let i = left; i <= mid; i++) {
while (j <= right && nums[i] > 2 * nums[j]) j++;
count += j - (mid + 1);
}
nums.slice(left, right + 1).sort((a, b) => a - b).forEach((n, idx) => nums[left + idx] = n);
return count;
}
return mergeSort(nums, new Array(nums.length), 0, nums.length - 1);
}#include <stdio.h>
int merge(int* nums, int* temp, int left, int mid, int right) {
int i = left, j = mid, k = left, count = 0;
while (i <= mid - 1 && j <= right) {
if ((long)nums[i] > 2 * (long)nums[j]) {
count += mid - i;
j++;
} else {
i++;
}
}
i = left;
j = mid;
while (i <= mid - 1 && j <= right) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
while (i <= mid - 1) temp[k++] = nums[i++];
while (j <= right) temp[k++] = nums[j++];
for (i = left; i <= right; i++) nums[i] = temp[i];
return count;
}
int mergeSort(int* nums, int* temp, int left, int right) {
int mid, count = 0;
if (right > left) {
mid = (right + left) / 2;
count += mergeSort(nums, temp, left, mid);
count += mergeSort(nums, temp, mid + 1, right);
count += merge(nums, temp, left, mid + 1, right);
}
return count;
}
int reversePairs(int* nums, int numsSize) {
int* temp = (int*)malloc(numsSize * sizeof(int));
int result = mergeSort(nums, temp, 0, numsSize - 1);
free(temp);
return result;
}public class Solution {
public int ReversePairs(int[] nums) {
if (nums == null || nums.Length == 0) return 0;
int[] temp = new int[nums.Length];
return MergeSort(nums, temp, 0, nums.Length - 1);
}
private int MergeSort(int[] nums, int[] temp, int left, int right) {
if (left >= right) return 0;
int mid = left + (right - left) / 2;
int count = MergeSort(nums, temp, left, mid) + MergeSort(nums, temp, mid + 1, right);
count += Merge(nums, temp, left, mid, right);
return count;
}
private int Merge(int[] nums, int[] temp, int left, int mid, int right) {
int i = left, j = mid + 1, k = left, count = 0;
while (i <= mid) {
while (j <= right && (long)nums[i] > 2 * (long)nums[j]) j++;
count += j - (mid + 1);
i++;
}
Array.Copy(nums, left, temp, left, right - left + 1);
i = left;
j = mid + 1;
k = left;
while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) {
nums[k++] = temp[i++];
} else {
nums[k++] = temp[j++];
}
}
while (i <= mid) nums[k++] = temp[i++];
while (j <= right) nums[k++] = temp[j++];
return count;
}
}This Python implementation makes use of merge sort to recursively split the array and count valid reverse pairs during the merge step.
Time Complexity: O(n log n).
Space Complexity: O(n).
Approach 3: Default Approach
func reversePairs(nums []int) int {
n := len(nums)
t := make([]int, n)
var mergeSort func(l, r int) int
mergeSort = func(l, r int) int {
if l >= r {
return 0
}
mid := (l + r) >> 1
ans := mergeSort(l, mid) + mergeSort(mid+1, r)
i, j, k := l, mid+1, 0
for i <= mid && j <= r {
if nums[i] <= nums[j]*2 {
i++
} else {
ans += mid - i + 1
j++
}
}
i, j = l, mid+1
for i <= mid && j <= r {
if nums[i] <= nums[j] {
t[k] = nums[i]
k, i = k+1, i+1
} else {
t[k] = nums[j]
k, j = k+1, j+1
}
}
for ; i <= mid; i, k = i+1, k+1 {
t[k] = nums[i]
}
for ; j <= r; j, k = j+1, k+1 {
t[k] = nums[j]
}
for i = l; i <= r; i++ {
nums[i] = t[i-l]
}
return ans
}
return mergeSort(0, n-1)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Naive Brute Force Approach | Time Complexity: O(n^2). |
| Optimized Merge Sort Approach | Time Complexity: O(n log n). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Brute Force | O(n^2) | O(1) | Good for understanding the problem or very small arrays |
| Merge Sort (Divide and Conquer) | O(n log n) | O(n) | Preferred solution for interviews and large inputs |
Frequently asked questions
Is Reverse Pairs easy or hard?
Reverse Pairs is classified as a hard problem on LeetCode. The difficulty comes from recognizing that brute force is too slow and applying a modified merge sort or advanced data structures to count pairs efficiently.
How to solve Reverse Pairs in O(n)?
An O(n) solution is not known for the general case because the problem requires comparing elements across many index combinations. The best practical approach is O(n log n) using merge sort, Binary Indexed Tree, or segment tree techniques.
What is the best approach for Reverse Pairs?
The most widely accepted solution uses a modified merge sort. During the merge step, both halves are already sorted, which allows efficient counting of pairs where nums[i] > 2 * nums[j]. This reduces the complexity from O(n^2) to O(n log n).
What data structure is used in Reverse Pairs?
Common solutions rely on merge sort with divide-and-conquer. Alternative implementations may use Binary Indexed Trees, segment trees, or ordered sets combined with coordinate compression to track counts efficiently.
What is the time complexity of Reverse Pairs?
The optimal merge sort solution runs in O(n log n) time with O(n) auxiliary space. A brute force approach that checks every pair requires O(n^2) time and is too slow for large arrays.
Is Reverse Pairs asked at Google, Amazon, or Meta?
Reverse Pairs is a well-known hard interview problem and has appeared in interviews at companies like Google, Amazon, and Meta. It tests understanding of divide-and-conquer algorithms, merge sort modifications, and advanced counting techniques.
Is there a Python or Java solution for Reverse Pairs?
Yes. The merge sort approach is commonly implemented in Python, Java, C++, and other languages. The logic remains the same: recursively split the array, count cross-half reverse pairs using two pointers, then merge the sorted halves.