We need to count pairs of indices (i, j) where i comes before j in the array and the element at i is strictly greater than twice the element at j. This is a modified inversion counting problem. In a standard inversion, the condition is nums[i] > nums[j]. Here, the condition is asymmetric: nums[i] > 2 * nums[j].

What makes this harder than ordinary inversion counting is that the counting condition and the sorting condition differ. In regular inversion counting with merge sort, you count and sort using the same comparison. Here, you count pairs satisfying nums[i] > 2 * nums[j] but still sort by plain value order. The two operations have to be decoupled.

The values can be as large as 2^31 - 1, so 2 * nums[j] overflows a 32-bit integer. The comparison needs long (64-bit) arithmetic.

Key Constraints:

Intuition

Check every pair (i, j) with i < j and count the ones where nums[i] > 2 * nums[j]. Two nested loops, testing the condition for each pair.

This gives a baseline to confirm correctness before optimizing.

Algorithm

Example Walkthrough

Code

This is too slow for n up to 50,000. The next approach reuses the structure of merge sort to count valid pairs while it sorts, bringing the cost down to O(n log n).

Intuition

During the merge step of merge sort, you hold two sorted halves, and every element in the left half originally appeared before every element in the right half. That positional guarantee matches the i < j requirement for a reverse pair: any pair we count with a left element before a right element automatically has the smaller index on the left.

The complication is that counting and sorting use different comparisons. In standard inversion counting both use nums[i] > nums[j]. For Reverse Pairs the counting condition is nums[i] > 2 * nums[j], while the merge still orders by plain value. The two cannot share a single pass, so we split the merge step into two phases:

Both phases run in O(n) time because both halves are sorted, so the overall cost stays O(n log n).

The count phase works as a single pass because the left half is sorted. As we advance to a larger left element, the right pointer never has to move backward: if left[i] > 2 * right[j], then left[i+1] >= left[i] > 2 * right[j], so every right element that paired with left[i] still pairs with left[i+1]. For each left element we extend the right pointer as far as left[i] > 2 * right[j] holds, and the count of valid right elements only grows.

Algorithm

Example Walkthrough

Code

Merge sort reaches the optimal O(n log n) but rearranges the input array. The next approach hits the same time bound with a Binary Indexed Tree and leaves the input untouched.

Intuition

Instead of sorting the array, process elements from right to left and maintain a count of the elements seen so far. For each element nums[i], count how many already-seen elements nums[j] (where j > i) satisfy nums[i] > 2 * nums[j]. Since nums[i] > 2 * nums[j] is equivalent to nums[j] < nums[i] / 2, and values are integers, the condition becomes nums[j] <= floor((nums[i] - 1) / 2). So each step is a "how many seen values are at most this threshold?" query.

A Binary Indexed Tree (BIT) answers that with point updates and prefix sum queries in O(log n) time. The value range spans the full 32-bit integer range, which is too large to index directly, so we apply coordinate compression: collect every value we will ever query or insert, sort and deduplicate them, and map each to a compact index.

Processing right to left is what enforces the i < j constraint: every element already in the BIT sits at a larger original index than the current one, so a value match is also a valid index pair.

Algorithm

Example Walkthrough

Code