Reverse Pairs
Hard · Arrays & Hashing · Array · Binary Search · Divide and Conquer · Binary Indexed Tree · Segment Tree · Merge Sort · Ordered Set
Problem
In an integer array nums, call a pair of indices (i, j) important when i 2 * nums[j].
Return the number of important pairs in nums. Values can be negative and as large as a 32-bit integer, so 2 * nums[j] may not fit in 32 bits.
Examples
Input: nums = [5,4,1,2] Output: 3
The pairs are (5, 1), (5, 2) and (4, 1). 4 > 2 · 2 fails because 4 is not greater than 4.
Input: nums = [2,3,6] Output: 0
No earlier value is more than twice a later one.
Input: nums = [-1,-3] Output: 1
-1 is greater than 2 · (-3) = -6.
Constraints
- 1 <= len(nums) <= 5 · 10^4
- -2^31 <= nums[i] <= 2^31 - 1
Approaches
- Check every pair — time O(n²), space O(1)
Follow-up
A Fenwick tree (binary indexed tree) also works: walk from left to right, and for each value count how many earlier values exceed twice it, using the ranks of all values and doubled values after coordinate compression. Same O(n log n), and it streams.
Related problems
Start free on Cariara · Coding problems · System design studio
