Imagine you have a row of numbers and you want the biggest sum of any 3 in a row. You could add up every group of 3 from scratch — but that repeats a lot of work. The sliding window trick keeps a running total and just slides it across, doing almost no work per step. It turns a slow O(n*k) scan into a fast O(n) one.
Step through the animation on the right. Watch the window (the blue cells between L and R) slide one spot at a time. Each slide drops one number on the left and picks up one on the right — the highlighted line of code shows exactly that.
The idea
A fixed-size window covers k cells. Add up those k cells once to get the first window sum. Now slide the window right by one: the leftmost cell leaves, a new cell enters. Instead of re-adding all k numbers, just subtract the one that left and add the one that entered. That is one subtraction and one addition per slide — no matter how big k is.
After each slide, compare the new window sum to the best you have seen and keep the larger one. When the window reaches the end, the best value is your answer.
Walk through it
Press Play on the right, or step with Next / Back. Notice three things:
- The cells inside the window turn blue. Pointers L and R mark its edges.
- On each slide, the cell that leaves turns gray (it is out of the window) and a new cell turns blue.
- The two labels track the live window sum and the best sum found so far. At the end, the winning window turns green.
The array is [2, 1, 5, 1, 3, 2] with k = 3. The first window [2, 1, 5] sums to 8. Slide once to [1, 5, 1] (sum 7), again to [5, 1, 3] (sum 9 — a new best), and once more to [1, 3, 2] (sum 6). The answer is 9.
The code, line by line
def max_sum_k(a, k):
n = len(a)
window = sum(a[:k]) # first window: add the first k
best = window
for r in range(k, n): # slide the right edge across
window += a[r] - a[r - k] # add new, drop old
best = max(best, window)
return best- Line 3 builds the first window by summing the first
kcells. This is the only time we add up a whole window from scratch. - Line 6 is the heart of the trick.
a[r]is the cell entering on the right;a[r - k]is the cell leaving on the left. Adding one and subtracting the other updates the sum in constant time. - Line 7 keeps the running best.
- Because each of the
ncells is added once and removed once, the whole scan isO(n).
Complexity
| Case | Time | Notes |
|---|---|---|
| Sliding window | O(n) (moderate) | each cell enters and leaves once |
| Naive (re-sum each window) | O(n*k) (moderate) | re-adds k numbers per window |
O(1) (fast)Why is the naive way O(n*k)? There are about n windows, and re-summing each one touches k cells, so the work is n × k. The sliding window avoids the repeat: when the window moves, only one cell changes on each side, so each step is constant work and the total is O(n). Space is O(1) because we only keep two numbers — the current sum and the best.
When to use / pitfalls
Reach for a sliding window whenever a problem asks about a contiguous run of a fixed size k
(max/min/average sum of k items, or "every window of k"). The pattern also extends to variable-size
windows — for example, "longest subarray with sum at most S" — where you grow R and shrink L based on a
condition instead of keeping the size fixed.
The classic bug is forgetting to subtract the element that left the window. If you only add a[r] and
never subtract a[r - k], your "window" keeps growing and the sum is wrong. Every slide must do both:
add the entering cell and drop the leaving cell.
Practice
For [2, 1, 5, 1, 3, 2] with k = 3, the window [2, 1, 5] sums to 8. After sliding once to [1, 5, 1], what is the new sum — and how do you get it without re-adding all three?
1. When the window slides right by one, what changes?
2. Why is the sliding window O(n) instead of O(n*k)?
3. In `window += a[r] - a[r - k]`, what is `a[r - k]`?
4. What is the space complexity of this sliding window?