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.length andnums[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 - 1Problem 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.
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.
This solution utilizes two loops to iterate over all pairs in the array, checking if they match the reverse pair condition.
Time Complexity: O(n^2) because of the nested loops.
Space Complexity: O(1) as it uses constant extra space.
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.
In this C implementation of the merge sort, we maintain a temporary array for merging while counting reverse pairs whenever we find an element in the left part that is greater than twice an element in the right part.
Time Complexity: O(n log n) due to merge sort steps.
Space Complexity: O(n) for the temporary array used in merging.
| Approach | Complexity |
|---|---|
| Naive Brute Force Approach | Time Complexity: O(n^2) because of the nested loops. |
| Optimized Merge Sort Approach | Time Complexity: O(n log n) due to merge sort steps. |
| 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 |
Reverse Pairs | Hard Interview Question • take U forward • 349,606 views views
Watch 9 more video solutions →Practice Reverse Pairs with our built-in code editor and test cases.
Practice on FleetCode