A fitness app stores how many thousand steps someone walked each day. Every value is positive. Write a function that returns the length of the shortest run of consecutive days whose total is at leastgoal. If no run reaches the goal, return 0.
text
1shortest_stretch([2, 3, 1, 2, 4, 3], 7) -> 2
2shortest_stretch([1, 4, 4], 4) -> 1
3shortest_stretch([1, 1, 1], 5) -> 0
Example 1
2
0
3
1
1
2
2
3
4
4
3
5
4 + 3 reaches 7 in two days.
In the first example, [4, 3] adds up to 7 in two days. No single day reaches 7.
Write shortest_stretch(steps, goal) in Python or shortestStretch(steps, goal) in JavaScript.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 20 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
Brute force
For every start day, keep adding days until the total reaches the goal, and record the length. That's O(n²). Can you avoid starting over for each start day?
Step 2
Grow the window until it's good enough
Move right forward, adding each day to a running total. As soon as the total reaches the goal, the window [left, right] is a candidate answer.
Step 3
Then shrink it while it stays good enough
While the total is still at least goal, record the window's length and remove steps[left] from the front (move left forward). Because every value is positive, removing a day always lowers the total, so you know exactly when to stop.
Step by step1 / 7
leftright
2
0
3
1
1
2
2
3
4
4
3
5
right reaches day 3: total 8, enough. Length 4.
Step 4
Why nothing is missed
For each right, after shrinking, left is as far right as it can go with the window still reaching the goal. That's the shortest window ending at right. The best of those is the answer.
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Slide a window over the days with a running total. Add steps[right] as right moves forward. While the total is at least goal, update the shortest length with right - left + 1, subtract steps[left] and move left on. If no window ever reached the goal, return 0.
python
1def shortest_stretch(steps, goal):
2 best = float("inf")
3 total = 0
4 left = 0
5 for right, value in enumerate(steps):
6 total += value
↑grow: add the new day
7 while total >= goal:
↑enough? then try shrinking
8 best = min(best, right - left + 1)
↑record BEFORE shrinking
9 total -= steps[left]
10 left += 1
11 return 0 if best == float("inf") else best
↑never reached the goal: 0
javascript
1function shortestStretch(steps, goal) {
2 let best = Infinity
3 let total = 0
4 let left = 0
5 for (let right = 0; right < steps.length; right++) {
6 total += steps[right]
↑grow: add the new day
7 while (total >= goal) {
↑enough? then try shrinking
8 best = Math.min(best, right - left + 1)
↑record BEFORE shrinking
9 total -= steps[left]
10 left++
11 }
12 }
13 return best === Infinity ? 0 : best
↑never reached the goal: 0
14}
Complexity
TimeO(n)SpaceO(1)
O(n) time: right moves n times and left moves at most n times in total. O(1) extra space.
What we learned
For "shortest window that satisfies a condition", record the answer inside the shrinking loop.
The window technique depends on all values being positive. Say that out loud: it's exactly what an interviewer wants to hear you check.
Return a clear "no answer" value (here 0) and test that case.