LeetCode 493 Reverse Pairs - Solution

You use modified merge sort. While merging, count pairs where left element > 2 * right element.

The trick is: during merge, both halves are sorted. You use two pointers: for each left element, count right elements where condition holds.

Example: [1,3,2,3,1]. When merging [1,3] and [2,3,1], you count pairs: 3 > 2*1 (yes).

Modified merge sort. For $n = 5 \times 10^4$: $O(n \log n)$ time, about $8 \times 10^5$ operations. $O(n)$ space.