Reverse Pairs Count

Count pairs i<j with nums[i] > 2*nums[j] using sorting + two pointers

arrays counting sorting two-pointers

Write a function `reverse_pairs(nums)` that returns the number of pairs (i, j) with 0 <= i < j < len(nums) such that `nums[i] > 2 * nums[j]`.

Your solution must run in O(n log n) time using a merge-sort or sorting + two-pointer approach. Do not use a naive O(n^2) double loop.

Function signature: `def reverse_pairs(nums: list) -> int:`

The list may contain up to 50,000 integers. The integers can be positive, negative, or zero. The result fits within a 64-bit signed integer.

Constraints

Input: a list of integers. Length n satisfies 0 <= n <= 50,000. Each integer is in the range [-10^9, 10^9]. Output: an integer count.

Complexity: O(n log n) time, O(n) extra space.

Example

>>> reverse_pairs([1,3,2,3,1])
2
>>> reverse_pairs([2,4,3,5,1])
3
>>> reverse_pairs([])
0

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about how merge sort can count such pairs while merging two sorted halves.

During merge, for each left element, count how many right elements satisfy the condition using two pointers.

If the array is sorted globally, you can use a Fenwick tree or a sorted list with bisect to count after each insertion.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.