Reverse Pairs
MetaThe problem
Given an integer array nums. Return the number of reverse pairs in the array.
An index pair** (i, j) **is called a **reverse **pair if:
-
0 <= i < j < nums.length
-
nums[i] > 2 * nums[j]
Input: nums = [6, 4, 1, 2, 7] Output: 3 Explanation: The reverse pairs are: (0, 2) : nums[0] = 6, nums[2] = 1, 6 > 2 * 1 (0, 3) : nums[0] = 6, nums[3] = 2, 6 > 2 * 2 (1, 2) : nums[1] = 4, nums[2] = 1, 4 > 2 * 1
Input: nums = [5, 4, 4, 3, 3] Output: 0 Explanation: No pairs satisfy both the conditons.
Input: nums = [6, 4, 4, 2, 2]
- 1 <= nums.length <= 5 * 104
- -231 <= nums[i] <= 231 - 1
cpp
class Solution {
public:
int reversePairs(vector<int>& nums) {
}
};java
class Solution {
public int reversePairs(int[] nums) {
}
}python
class Solution:
def reversePairs(self, nums):javascript
class Solution {
reversePairs(nums) {
}
}csharp
public class Solution {
public int ReversePairs(int[] nums) {
}
}go
func reversePairs(nums []int) int {
}Stuck? Show a way to structure it+
- 01Split recursively
- 02Count pairs across sorted halves
- 03Advance right pointer monotonically
- 04Use a wide numeric comparison
- 05Merge normally
Reference answer
Then expect these follow-ups
Why does j never need to move backward?
Tests: correctness reasoning
How would a Fenwick-tree approach compare?
Tests: follow-up reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question