Algorithms · intermediate
Sliding window
A sliding-window algorithm maintains an aggregate for a contiguous range and updates it as the boundaries move, reusing prior work instead of recomputing each range from scratch.
Why it matters
It converts many contiguous substring and subarray problems from quadratic enumeration to linear or near-linear processing.
Mental model
How to reason about sliding window
The window is the current candidate interval. Expanding adds one element to its state; shrinking removes one, and a validity rule decides which boundary moves next.
Analogy
A scanner frame moves across a film strip: each step drops the frame that left and includes the new frame that entered rather than rereading the whole reel segment.
Examples
See the boundary, not just the happy path
Worked example · Fixed-size average
sum += a[right] - a[right-k]One addition and one subtraction update each size-k window, yielding Theta(n) work instead of Theta(nk).
Worked example · Longest unique substring
expand right; move left past a repeated characterA frequency map preserves the no-duplicates invariant while each boundary moves forward at most n times.
Useful contrast · Negative values break the shrink rule
find a subarray with sum >= 3 in [2, -5, 3]A positive-number window never becomes valid as it expands here, so it never drops the negative prefix and misses the valid suffix [3]. The movement rule needs monotonicity.
Common mistakes
Misconceptions to remove early
Recomputing the window state
Summing or scanning the whole window after every move restores quadratic work. Update only what entered and left.
Applying a variable window without monotonicity
For example, negative numbers can break the usual 'shrink while sum is too large' reasoning because shrinking need not decrease the sum.
Quick check
Can you predict the result?
1. Why is a fixed-size rolling sum Theta(n) rather than Theta(nk)?
- • Each step adds the entering value and removes the leaving value in constant time
- • The window is sorted before every move
- • Only the first window is examined
2. What must be justified for a variable-size sliding window?
Keep building