Reverse Pairs

Hard· Fenwick tree· merge sort

Problem

Count the pairs of indices i < j in an integer array where nums[i] is more than twice nums[j]. Values can be large or negative, so be careful with overflow.

Examples

Input: nums = [1,3,2,3,1]

Output: 2

(3, 1) at indices 1,4 and 3,4.

Input: nums = [2,4,3,5,1]

Output: 3

Constraints

• 1 <= nums.length <= 5·10^4
• -2^31 <= nums[i] <= 2^31 - 1

Hints & approach

Hint 1

Checking every pair is O(n²) — too slow.

Hint 2

Scanning left to right, for each nums[j] you need the count of earlier values greater than 2·nums[j].

Hint 3

Coordinate-compress all values and all doubled values, then query a Fenwick tree.

Approachtry the hints first

Collect every nums[i] and every 2·nums[i] (using 64-bit arithmetic) and compress them to ranks. Scan left to right; for each x, the pairs ending here are the number of earlier values with rank greater than rank(2x), which is total seen minus a Fenwick prefix sum. Then insert rank(x). Modified merge sort, counting with a second pointer before merging, is an equally good O(n log n) solution.

Time O(n log n) · Space O(n)

← PreviousCount of Smaller Numbers After Self Next →Count of Range Sum