BeginnerSliding Window
Fixed-size windows: add one, drop one
Summing every window of size k? Don't re-add k numbers each time: add the one entering and subtract the one leaving.
The idea
Neighbouring windows share all but two elements. Re-summing each window costs O(k) per window, O(n·k) in total. Instead keep a running sum and update it in O(1) as the window slides.
Worked example
Max average of size-3 windows in [1, 12, -5, -6, 50, 3]
- First window 1 + 12 − 5 = 8
- Slide: + (−6) − 1 = 1
- Slide: + 50 − 12 = 39
- Slide: + 3 − (−5) = 47 → best sum 47, average 47/3
In code (Python)
def max_average(nums, k):
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k]
best = max(best, window)
return best / kO(n) time, O(1) space.
How to spot it
- “every subarray of length k”, “window of size k”.
Common mistakes
- Subtracting nums[i - k + 1] instead of nums[i - k] (off by one).
- Starting best at 0 when sums can be negative.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →