Reverse Pairs
Problem Description
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
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The problem asks us to count the number of important reverse pairs (i, j) such that i < j and nums[i] > 2 * nums[j]. A straightforward approach is to evaluate every possible pair (i, j) and check the condition. This leads to a simple double loop solution.
Steps:
- Iterate over each pair
(i, j)wherei < j. - For each pair, check if
nums[i] > 2 * nums[j]. - Count all such pairs.
Code:
- Time Complexity: O(n²), where
nis the number of elements innums. We check each pair(i, j)once. - Space Complexity: O(1), as we are utilizing only a constant amount of extra space.
2. Merge Sort with Modification
Intuition:
The brute-force solution is inefficient for large inputs. By using a modified version of merge sort, we can efficiently count reverse pairs. The essential insight is to leverage the sorted order of the array to count pairs more efficiently.
Steps:
- Use merge sort to sort the array.
- During the merge process, for each left element, count how many elements in the right sorted array satisfy the reverse pair condition.
- Count and merge both parts of the array while maintaining the order.
Code:
- Time Complexity: O(n log n), where
nis the number of elements innums. This includes splitting the array (log nlevels) and merging subarrays (O(n)per level). - Space Complexity: O(n), due to the temporary arrays used during merge steps.