Count Reverse Pairs
Advanced
A reverse pair is a pair of positions i < j with nums[i] > 2 * nums[j]. Count them.
The starter code checks every pair. It is correct but too slow for long lists. Make it fast.
Examples
Example 1
Input:
count_reverse_pairs([1, 3, 2, 3, 1])
Output:
2
The pairs are (3, 1) at positions 1, 4 and (3, 1) at positions 3, 4.
Example 2
Input:
count_reverse_pairs([2, 4, 3, 5, 1])
Output:
3
The pairs are (4, 1), (3, 1) and (5, 1).
Constraints
0 <= len(nums) <= 5 * 10**4-10**9 <= nums[i] <= 10**9
Theory
Go to TheoryKeywords
dsa-sheetarrayshard-arrays
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.