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
Hiring now
Get the Meta interview, not just the prep
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Next question