What Is a Sliding Window?
A Sliding Window slides a contiguous range (window) one step at a time across an array, maintaining values like a range sum or max in O(n). Recomputing the range from scratch each time is O(nk); updating by adding the entering value and subtracting the leaving one drops it to O(n).
The one-line idea: "don't recompute the overlap." Moving one step leaves most of the window unchanged.
Two Kinds of Window
- •Fixed-size window: the size
kis set, and you push one step right. Problems like "max sum of k consecutive elements." - •Variable-size window: grow the right end until a condition holds, and shrink the left when it breaks (the same-direction version of two pointers). Problems like "shortest length with sum ≥ target."
How It Works (Fixed Size)
Step 1. Compute the sum of the first k elements.
Step 2. When sliding right one step, update with sum += arr[r] (the entering value) and sum -= arr[l] (the leaving value).
Step 3. Check the max or condition on each move.
For a variable window, keep growing the right; when a condition is violated, shrink the left with a while until it holds again, tracking the optimal length.
The AlgoNote visualization shows which value is added and which leaves as the window slides, step by step.
Time and Space Complexity
| Complexity | |
|---|---|
| Time | O(n) |
| Space | O(1) ~ O(k) |
Each element enters and leaves the window once, so it's O(n) overall.
Walking Through an Example
Max range sum of [2, 1, 5, 1, 3, 2] with k = 3:
- •first window [2,1,5] = 8
- •step → +1 −2 → 7 ([1,5,1])
- •step → +3 −1 → 9 ([5,1,3]) ← max
- •step → +2 −5 → 6 ([1,3,2])
- •answer: 9
Common Mistakes
- •Forgetting to subtract the leaving value: adding only the entering value turns it into a prefix sum, not a window.
- •Variable-window boundary: when shrinking the left, use a
while(notif) to recover the condition fully. - •Empty window / k > n: handle edge cases like a window larger than the input first.
See It in Action on AlgoNote
Watch a new value get added and an old one leave as the window slides right and the range value updates, step by step on AlgoNote.