Stretches With Total in a Band
Problem
A trading desk reviews a day's sequence of profit and loss figures pnl (gains positive, losses negative). A stretch is a non-empty run of consecutive figures; its total is the sum of its figures.
Given lower and upper, return how many stretches have a total t with lower ≤ t ≤ upper.
Example 1
- Input:
- pnl = [3, -2, 4, 1], lower = 2, upper = 5
- Output:
- 6
[3] = 3, [3, -2, 4] = 5, [-2, 4] = 2, [-2, 4, 1] = 3, [4] = 4 and [4, 1] = 5 fall in the band.
Example 2
- Input:
- pnl = [0, 0], lower = 0, upper = 0
- Output:
- 3
[0], [0] and [0, 0] all total 0.
Constraints
- 1 ≤ pnl.length ≤ 5 · 10^4
- -2^31 ≤ pnl[i] ≤ 2^31 - 1
- -10^5 ≤ lower ≤ upper ≤ 10^5
Hint
Show the first hint
Rewrite a stretch total with prefix sums: total(i..j) = P[j + 1] - P[i]. What are you counting now?
Walkthrough
How to approach it
01Clarify before coding
- Is the band inclusive? Yes, both ends.
- Can sums overflow 32 bits? Yes, prefix sums reach about 10^14; use 64-bit values (safe in JavaScript numbers).
- Are empty stretches counted? No, a stretch has at least one figure.
02Brute force
Fix each start, extend the end while accumulating the sum, and count totals inside the band.
Cost: O(n²): 1.25·10^9 additions 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.