What is the sliding window pattern?
Sliding window maintains information about a contiguous range of an array or string while one or both boundaries move forward. The stored information might be a sum, a frequency map, a count of distinct values, or the number of items violating a condition.
The optimization comes from overlap. If one window covers indexes 0 through 2 and the next covers 1 through 3, the two windows share indexes 1 and 2. Re-summing all three items throws away useful work. A rolling sum subtracts the value at index 0 and adds the value at index 3.
The stored window state exactly describes the current contiguous range [left, right]. Whenever a boundary moves, update the state so that statement remains true.
Fixed-size vs. variable-size windows
| Window type | What controls movement? | Typical question |
|---|---|---|
| Fixed size | A required length k | Best sum or average among all contiguous blocks of size k |
| Variable size | A validity condition | Longest valid range or shortest range reaching a threshold |
For a fixed window, build the first range, then move both boundaries together. For a variable window, usually expand the right boundary to gain information and move the left boundary only while the range needs to shrink or can be improved.
Step-by-step: maximum sum of size 3
Find the maximum sum among all length-3 contiguous subarrays of [2, 1, 5, 1, 3, 2].
Build the first three-value window.
- First window: 2 + 1 + 5 = 8.
- Subtract 2 and add 1: sum 7.
- Subtract 1 and add 3: sum 9.
- Subtract 5 and add 2: sum 6. Maximum is 9.
Every window after the first costs O(1) to update. The running sum remembers the shared middle of the range.
Reusable window outlines
Fixed-size window
windowState = state of first k items
best = windowState
for right from k to values.length - 1:
add values[right] to windowState
remove values[right - k] from windowState
update best
return bestVariable-size window
left = 0
windowState = empty
for right from 0 to values.length - 1:
add values[right] to windowState
while window is invalid (or can shrink):
remove values[left] from windowState
left += 1
update answer using [left, right]The exact order of “shrink” and “record answer” depends on the question. Write the validity condition in plain language before code.
Why can two moving boundaries still be O(n)?
In a standard forward-only sliding window, the right boundary visits each item once and the left boundary also moves across the sequence at most once. A nested while loop does not automatically make the algorithm O(n²): across the entire run, each value enters and leaves at most once. The total is O(n) time.
Extra space depends on the stored state. A rolling sum is O(1). A frequency map may grow to O(k), O(alphabet size), or O(n), depending on the problem.
Common sliding window mistakes
- Using it for a non-contiguous choice: a window always represents a consecutive range.
- Updating only one side of the state: add what enters and remove what leaves.
- Recording at the wrong time: decide whether the answer is measured before, during, or after shrinking.
- Losing frequency-map cleanup: remove keys when their count reaches zero if distinct-count logic depends on map size.
- Assuming every variable window works: some conditions are not monotonic enough for one-direction shrinking.
“Adjacent windows share most of their elements. I maintain exactly the state for the current range, then update it locally as each boundary moves.”
Continue learning
Move useful positions to remove impossible work.
COMPARE →Binary searchShrink an ordered search space by half.
NEXT PATTERN →Watch the range move
Practice sliding window visually on iPhone.
Learn the signal, preserve the invariant, shape the outline, and review mistakes with spacing.
