Sliding Window
Maintain a window of elements over a sequence; expand/shrink to satisfy a constraint while tracking an aggregate.
Contiguous subarray or substring problems — longest, shortest, max-sum, or constraint-bounded windows.
Each element enters and exits the window at most once, so total work across both pointers is linear. Space is O(k) for whatever state the window tracks (frequency map of distinct chars, k-size deque, etc.).
The same idea applied in production systems — read these once you know the pattern to see where it lands in the real world.
The sliding window pattern tracks a contiguous range over a sequence using two indices, expanding by moving the right index and shrinking by moving the left. State within the window (sum, count, frequency map) is updated incrementally as elements enter and leave — this is what makes it O(n) instead of recomputing per window.
The shape of the window varies by problem. Fixed-size windows answer "best over all length-k substrings"; variable-size windows answer "longest/shortest satisfying constraint X". The shrink condition is the heart of the variant: shrink while the window violates the constraint, or shrink to the smallest valid window.
The win compared to nested loops is moving from O(n*k) or O(n^2) down to O(n) by reusing work across windows instead of recomputing. The pattern only works when the window's invariant can be updated in O(1) (or amortized O(1)) per pointer move — otherwise you're back to recomputation.
Each element enters and leaves the window at most once, so amortized work is O(n) — the inner while loop doesn't make the algorithm O(n^2).
- Forgetting to update window state when shrinking — e.g. decrementing a frequency map entry as left moves past it, or leaving stale zero-count keys in the map.
- Using >= vs > in the shrink condition off by one, returning a window of length len-1 or len+1.
- Tracking the window's running aggregate (sum/product) in a way that breaks for zero or negative values when the problem implicitly assumes positives.
- Updating the answer at the wrong time — after shrinking when the problem wants the largest valid window, or before shrinking when it wants the smallest.
- Confusing 'at most k' with 'exactly k' problems: 'exactly k' usually requires atMost(k) - atMost(k-1).
- Fixed-size window: no while loop — just slide right and subtract the element falling off the left.
- Longest/shortest substring with constraint: variable window with a frequency map, shrink while invariant violated.
- Sliding window maximum / median: pair the window with a monotonic deque or two heaps for O(log k) or amortized O(1) extrema.
- Counting subarrays with property: use atMost(k) - atMost(k-1) to convert 'exactly' into two sliding-window passes.
int left = 0;
int best = 0;
// initialize window state (counts, sum, etc.)
for (int right = 0; right < n; right++) {
// expand: include arr[right] in window state
while (/* window is invalid */) {
// shrink: remove arr[left] from window state
left++;
}
best = Math.max(best, right - left + 1);
}
return best;Problems using this pattern
8Easiest first · Blind 75 above NeetCode 150