Sliding Window

A window that slides, grows, or shrinks across contiguous data — never resumming what it already knows

Fixed widthsubtract the outgoing, add the incoming
Grow and shrinkright extends, left tightens on demand
State, not resuma running total or map, updated in O(1)
Contiguous is the signalsubarray/substring + a condition means try this first

1.Fixed-size window (e.g. max sum of size-k subarray)

A fixed-size window of exactly k elements slides across an array one step at a time — only the element leaving and the element entering change the running total, so nothing needs to be resummed.

Key features

Turns an O(n × k) brute force ("resum every window") into O(n) — each element enters and leaves the window exactly once
The window size k stays the same for the entire scan — it never grows or shrinks
Needs one O(k) pass up front to build the first window before sliding begins

A fixed window updates by subtracting the outgoing element and adding the incoming one — resumming the whole window at every position is the O(n × k) trap this pattern exists to avoid.

2.Variable-size window that grows/shrinks based on a condition

A variable-size window grows by moving its right edge forward, and shrinks by moving its left edge forward whenever a condition demands it — the width adapts to the data instead of staying fixed.

Key features

left and right each only ever move forward — across the whole scan, both together take at most 2n steps, so the pattern is still O(n), not O(n²)
The exact shrink condition is problem-specific: "sum exceeds a limit," "a character repeats," "fewer than k distinct values remain"
Every valid window width is a candidate answer — check or record it right after a successful extension or shrink, not only once at the end

Shrink with a while, not an if — a window that is still valid after one shrink might stay valid after several more, and only the while keeps checking.

3.Window state maintained incrementally (not recomputed each shift)

A sliding window's state — a running sum, a frequency map, a count of distinct values — should be updated by exactly what changed as the window moves, never rebuilt from scratch at each position.

Key features

Rebuilding a frequency map from scratch at every window position turns an O(n) sliding window into O(n × window size) — the same trap a resummed fixed window falls into
A count reaching exactly 0 should DELETE that key, not just leave it at 0 — otherwise len(counts) overcounts how many distinct values are actually present in the window
This is not limited to sums and counts — a running MAXIMUM needs a monotonic deque instead of a plain variable, since removing the leaving element is not a simple subtraction

A window state is updated by what entered and what left, never rebuilt — and a count must be deleted at zero, not left sitting there, or a distinct-count check like len(counts) will lie.

4.Longest substring without repeating characters

The longest run of a string with no repeated character comes from a variable-size window that jumps its left edge past a duplicate the instant one appears, tracking the widest duplicate-free window seen.

Key features

O(n) time — each character is visited once by right, and left only ever jumps forward, never backward, across the whole scan
Storing the LAST SEEN INDEX (a dict) instead of just a set lets left jump straight past a duplicate in one step, instead of shrinking one character at a time
The seen-index check must also confirm the earlier occurrence is still INSIDE the window (last_seen[ch] >= left) — an occurrence from before the window started should not move left backward

Only jump left past a duplicate whose last-seen index is still inside the window (>= left) — an occurrence from before the window started must not move left backward.

5.Minimum window substring

The smallest window in one string that contains every character of another (with repeats) is found by growing the window until it qualifies, then shrinking it from the left as far as possible while it still does.

Key features

O(n + m), where n is the search string's length and m the target's — left and right each move forward at most n times total
One integer counter ("how many required slots are still unfilled") avoids re-checking the entire required-count dict on every step
A character not in the target can still be tracked in the counts dict, but it never affects the unfilled counter, since it was never required

Track how many required slots remain unfilled with one counter, and only shrink past characters the window has a surplus of — pulling in a still-needed one breaks validity.

6.Longest substring with at most K distinct characters

The longest substring with at most k distinct characters grows the window while a frequency map holds k or fewer keys, and shrinks from the left the moment a (k+1)th distinct character shows up.

Key features

"At most k" (not exactly k) means a string made of a single repeated character is always valid, for any k >= 1
A key must be DELETED at count 0, not just left at 0 — otherwise len(counts) overcounts how many distinct characters remain in the window
Changing the shrink condition to `!= k` instead of `> k` is the entire difference between this and an "exactly k distinct" variant — the surrounding structure is identical

Grow the window freely, but shrink the moment the frequency map holds more than k distinct keys — and always delete a key at count 0, or the distinct-key count itself becomes wrong.

7.Recognizing "contiguous subarray/substring satisfying X" as a sliding-window signal

Whenever a problem asks about a CONTIGUOUS subarray or substring — not any subset, specifically an unbroken run — that satisfies a condition on its sum, length, or character composition, try a sliding window before anything heavier.

Key features

The giveaway phrasing is "contiguous subarray" or "substring" combined with a sum/length/distinct-count/character condition
If elements can be removed or reordered — not required to stay contiguous — a sliding window does not apply; that shape usually points to sorting, hashing, or DP instead
A fixed target size ("subarray of length k") signals a fixed-size window; an open-ended condition ("smallest subarray with sum >= target") signals a variable-size one

Contiguous plus a condition on sum, length, or composition is the sliding-window signal — a fixed size means a fixed window, an open-ended condition means a variable one.

Spotted a mistake on this page? Tell us.

Read Sheet