Shortest Stretch Reaching Target
MediumSliding Window
Problem
A solar farm logs the energy produced each minute in nums (all positive). To charge a battery you need at least target units from consecutive minutes.
Return the length of the shortest run of consecutive minutes whose total is at least target, or 0 if no run is enough.
Example 1
- Input:
- nums = [1, 4, 2, 5, 3], target = 9
- Output:
- 3
4 + 2 + 5 = 11 and 2 + 5 + 3 = 10 both work with 3 minutes; no two adjacent minutes reach 9.
Example 2
- Input:
- nums = [1, 1, 1], target = 5
- Output:
- 0
Even the whole array only sums to 3.
Constraints
- 1 ≤ nums.length ≤ 10^5
- 1 ≤ nums[i] ≤ 10^4
- 1 ≤ target ≤ 10^9
Hint
Show the first hint
All values are positive. What happens to the sum when you extend a window to the right, or shrink it from the left?
Walkthrough
How to approach it
01Clarify before coding
- Are all values positive? Yes; that is what makes the two-pointer window valid.
- What if no run reaches target? Return 0.
- Is 'at least' inclusive? Yes, a sum equal to target counts.
02Brute force
For each start i, add elements to the right until the sum reaches target and record the length.
Cost: O(n²) time in the worst case (when target is large), about 5·10^9 steps for n = 10^5.
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.