Longest under-budget stretch: hints, no solution
Medium · Sliding window
A battery farm logs its hourly energy intake as non-negative whole numbers of kilowatt-hours. Before starting a maintenance job, the engineers want the longest stretch of consecutive hours in which the total intake stays within an energy budget, meaning the total is at most the budget.
Return the number of hours in the longest such stretch. Zero readings are allowed and cost nothing. If even a single hour exceeds the budget on its own, that hour cannot be part of any stretch, and if no hour qualifies the answer is 0.
Examples
- Input
- readings = [2, 1, 3, 1, 1, 4, 1], budget = 5
- Output
- 3
- Note
- The stretch 1, 3, 1 totals 5, and no longer stretch stays within 5.
- Input
- readings = [4, 5], budget = 3
- Output
- 0
- Note
- Every reading is above the budget of 3.
- Input
- readings = [0, 0, 0], budget = 0
- Output
- 3
- Note
- All zero readings fit in the budget of 0.
Constraints
- 0 <= readings.length <= 250000
- 0 <= readings[i] <= 1000
- 0 <= budget <= 2500000
Hint 1: a nudge
If a stretch is within budget, what can you say about every shorter stretch inside it?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.