Algorithms - sliding window

Sliding window is two-pointers with a constraint: the window represents a candidate, the answer is some aggregate over the window, and you maintain the aggregate incrementally. Recomputing on every shift is the rookie mistake — incremental update is the entire point.

Three flavors

Fixed-size. Window of length k, slide once per step. Maintain sum / max / counter incrementally — O(n). Anything that says “subarray of size k” is this.

Variable-size, expand-then-shrink. Right pointer always advances; left advances until the window is valid. The classic for “longest substring without repeats,” “minimum window covering,” “longest substring with at most k distinct.”

Variable-size with auxiliary structure. Same as above, but the validity predicate needs more than a counter — typically a hash map of frequencies plus a matched count to avoid re-scanning the map every step.

The “matched count” trick

For “minimum window containing all chars of T”: don’t compare the full window counter to the target counter every step (O(alphabet) per step). Instead:

• Track formed = how many distinct chars in the window have hit their required count.
• On expand: increment window[c]; if it now equals target[c], increment formed.
• On shrink: if window[c] was equal to target[c] and you’re about to decrement, decrement formed first.
• Window is valid iff formed == |target|.

This is what gets you to O(n) instead of O(n × alphabet).

Monotonic deque, for max/min over window

Sliding-window maximum: maintain a deque of indices where values are monotonically decreasing. The front is always the max. Push: pop tail while smaller. Pop front when it falls out of the window. Each index is pushed and popped once → O(n).

This generalizes — any “window aggregate that is order statistic” wants a monotonic deque or a heap (with lazy deletion).

When it doesn’t apply

Sliding window assumes the answer is some function of a contiguous range and the validity predicate is monotone in the window. Non-contiguous (subset, subsequence) → backtracking or DP. Non-monotone (predicate flips on/off as window grows) → it’s still tractable but you can’t assume the “shrink until valid” loop.