A sliding window is a sub-range [left, right] of an array or string that you grow and shrink as you scan. By reusing the work from the previous position instead of recomputing, it turns an O(n²) brute force into a single O(n) pass.
Fixed vs variable windows
A fixed window has a constant size k: slide it by adding the new element and removing the old one. A variable window grows its right edge and shrinks its left edge only when a condition is violated.
Maximum sum of k consecutive elements
windowSum = sum of first k elements
best = windowSum
for right = k to n-1:
windowSum += A[right] - A[right - k] // add new, drop old
best = max(best, windowSum)
return bestO(n)→O(1)
Each element enters and leaves the window once.
⚡ The edge
- Don't re-sum the window. For a fixed window, add the incoming element and subtract the outgoing one — that is the whole trick that makes it O(n) instead of O(n·k).
- For a variable window, only the left pointer shrinks the window, and only when the rule breaks; the right pointer always moves forward.
Worked example
Find the maximum sum of any 3 consecutive elements in [2, 1, 5, 1, 3, 2].
- First window [2,1,5] sums to 8; set best = 8.
- Slide right: drop 2, add 1 -> [1,5,1] = 7; then drop 1, add 3 -> [5,1,3] = 9; then drop 5, add 2 -> [1,3,2] = 6.
- The largest window sum seen is 9.
Answer: Maximum sum = 9 (the window [5,1,3])
⚠ Watch out
- Recomputing the whole window each step makes it O(n·k) — update incrementally instead.
- For variable windows, shrink with a while loop, not a single step — several lefts may need removing.
- Track what the window contains (a sum, a count, a frequency map) consistently as it moves.