Pairs More Than Double Later
Problem
A fraud monitor flags sharp drops in a series of daily balances balances. A pair of days i < j is a sharp drop when the earlier balance is strictly more than twice the later one: balances[i] > 2 * balances[j].
Return the number of sharp-drop pairs. Balances may be negative.
Example 1
- Input:
- balances = [6, 2, 5, 1]
- Output:
- 3
(6, 2): 6 > 4. (6, 1): 6 > 2. (5, 1): 5 > 2. The pair (2, 1) does not count because 2 > 2 is false.
Example 2
- Input:
- balances = [1, 1, 1]
- Output:
- 0
Example 3
- Input:
- balances = [-1, -3]
- Output:
- 1
-1 > 2 · (-3) = -6.
Constraints
- 1 ≤ balances.length ≤ 5 · 10^4
- -2^31 ≤ balances[i] ≤ 2^31 - 1
Hint
Show the first hint
This looks like counting inversions, but with a different condition. Why can't you count it inside the merge comparison itself?
Walkthrough
How to approach it
01Clarify before coding
- Is the comparison strict? Yes: x > 2y, so equal-to-double does not count.
- Can 2 · balance overflow? In 32-bit languages yes; use 64-bit arithmetic. Python and JavaScript numbers are safe here.
- How do negatives behave? Normally: -1 > 2 · (-3) = -6 is a sharp drop.
02Brute force
Check every pair i < j.
Cost: O(n²): 1.25·10^9 checks for n = 5·10^4.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.