The problem
Count pairs (i, j) with i < j and nums[i] > 2 × nums[j].
Stuck? Reveal hints one at a time
How to approach it
- 1Recursively sort-and-count each half; pairs within a half are counted by recursion.
- 2Cross pairs: for each left element (sorted), advance a right pointer while left > 2 × right; the pointer never retreats.
- 3Then do the standard merge to keep the invariant for the parent call.
- 4Sum of three counts is the answer.
Key insight
Sortedness makes the count monotone: as the left element grows, the qualifying right prefix only extends — so counting is amortized O(n) per level despite being a different predicate than the merge.
The solution
Watch out for
- You cannot fold the counting into the merge — the predicates differ (2× vs plain >).
- 2 × nums[j] can overflow 32-bit ints; use 64-bit or Python.