Sliding Window
Arrays: lesson 3 of 8
Reuse the last answer instead of recomputing it.
Lesson 3 of 8 · 5 min
Sliding Window
Step 1 of 7
window12best12
k=3
1
9
2
6
3
7
4
5
The first window is the only one you ever add up from scratch: 1 + 9 + 2 = 12.
The Idea
A window is a contiguous run of elements. Instead of rebuilding each window from scratch, add the element entering and subtract the one leaving. The cost drops from O(n·k) all the way to O(n).
Real-World Example
Your fitness tracker shows a rolling seven-day step average. Each morning it adds today's steps and drops the ones from eight days ago, rather than re-adding an entire week of numbers.
The Code
def max_window_sum(nums, k):
window = sum(nums[:k]) # the first window
best = window
for i in range(k, len(nums)):
window += nums[i] # element enters
window -= nums[i - k] # element leaves
best = max(best, window)
return best
# max_window_sum([1, 9, 2, 6, 3], 2) -> 11Your turn
Put the steps in the right order.
- Subtract the element leaving the window
- Sum the first k elements
- Update the best answer seen so far
- Add the next element entering the window
Mini quiz
1 / 3