1314. Budget Stretch With Refunds
A shop keeps a daily ledger where nums[i] is the net amount spent on day i. A positive value is a purchase and a negative value is a refund, so the running total of a stretch of days can go up and down.
Return the length of the longest non-empty stretch of consecutive days whose amounts add up to at most budget. The budget can be zero or even negative, in which case the stretch must be net refunds. If no stretch satisfies the condition, return 0.
Because refunds are allowed, shrinking a stretch does not always lower its total, so the usual single-pass window does not work. Use prefix sums and look at running maxima from the left and running minima from the right, which both only move in one direction. The intended solution runs in O(n) time and O(n) space.
Example 1
- Input:
- nums = [3,-2,4,-5,1], budget = 1
- Output:
- 5
- Explanation:
The stretch [3, -2, 4, -5] sums to 0, which is within the budget of 1, and the whole array sums to 1, so all 5 days fit.
Example 2
- Input:
- nums = [5,6,7], budget = 4
- Output:
- 0
- Explanation:
Every single day costs more than 4, so no stretch fits and the answer is 0.
Example 3
- Input:
- nums = [-4,2,-3], budget = -5
- Output:
- 3
- Explanation:
The stretch [-4, 2, -3] sums to -5, which meets the budget, so the answer is 3.
Constraints
-
1 ≤ nums.length ≤ 2 * 105 -
-104 ≤ nums[i] ≤ 104 -
-109 ≤ budget ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)