Count Reverse Pairs

Problem

Count the pairs (i, j) with i < j and nums[i] > 2 * nums[j].

Adapt merge sort: before each merge, advance a pointer over the sorted right half while the condition holds, adding the pointer count for every left element. Counts accumulate across all merge levels.

Hint

Both halves are sorted before counting, so the pointer over the right half only moves forward.

Test cases

case 1

in: [[1,3,2,3,1]]

expected: 2

case 2

in: [[2,4,3,5,1]]

expected: 3

case 3

in: [[-5,-5]]

expected: 1

case 4

in: [[5,4,3,2,1]]

expected: 4

case 5

in: [[]]

expected: 0

Starter codePython

def count_reverse_pairs(nums):
    # Your code here
    pass

5 test cases · run your code against them in the editor