Sliding Window Technique — Recognition, Template, Three Walkthroughs

The sliding window is one of those techniques that feels obvious after you've seen it, and impossible before. This post is about the "before" — the recognition step that turns a wall of code you memorised into a tool you can reach for on a problem you've never seen.

Recognition — when to reach for it

Sliding window is the right tool when all four of these hold:

The input is a linear sequence — array, string, or stream — and the answer is a contiguous slice of it.
You're asked for a longest, shortest, maximum, minimum, or count of subarrays satisfying some constraint.
The constraint is local enough that you can decide, in O(1) or O(k), whether the current window is valid.
The brute force is O(n²) — try every (left, right) pair — and most of that work is recomputing state you already had one step earlier.

If any of those breaks, sliding window is either the wrong tool or a red herring. Non-contiguous subsequences want DP. Constraints that need the whole array in view want prefix sums or segment trees. Multiple non-overlapping regions want a scan with state, not a window.

Mental model — why it collapses to O(n)

Two indices bound a window: left and right. right moves forward on every iteration, adding one element. left moves forward only when the window becomes invalid, removing elements from the left until it's valid again.

The magic: each element enters the window exactly once (when right sweeps past it) and leaves at most once (when left sweeps past it). Total work is at most 2n — every element is touched twice — regardless of how the window resizes. That's O(n).

Two flavours worth naming, because they have subtly different loop shapes:

Fixed-size — the window has constant width k. right - left + 1 == k for the whole scan. This is the friendliest introduction ("max sum subarray of size k") but you rarely see it in real interview problems.
Variable-size — the window grows and shrinks based on a constraint. This is where the pattern earns its keep. Every problem below is variable-size.

Within variable-size, there's a second split that trips people up: are you looking for the largest valid window, or the smallest valid window?

Largest valid: shrink left until the window is valid again, then measure. (LC 3.)
Smallest valid: shrink left while the window is still valid, measuring on each step. (LC 209, LC 76.)

Get this axis right and the code writes itself. Get it wrong and you'll be off-by-one in three places.

The template

def sliding_window(sequence):
    left = 0
    state = init_state()
    best = init_best()

    for right in range(len(sequence)):
        add_to_state(state, sequence[right])

        # "while invalid, shrink" for LARGEST-VALID problems
        # "while valid, shrink and record" for SMALLEST-VALID problems
        while should_shrink(state):
            remove_from_state(state, sequence[left])
            left += 1
            # smallest-valid: measure here, inside the shrink loop

        # largest-valid: measure here, after the shrink loop
        best = update(best, right - left + 1)

    return best

Everything below is one of three fillings for those blanks: what state is, what "valid" means, and which shrink shape applies.

Walkthrough 1 — LeetCode 209, Minimum Size Subarray Sum

Given an array of positive integers and a target, return the length of the shortest contiguous subarray whose sum is ≥ target. Return 0 if none exists.

Recognition. Contiguous ✓. Shortest ✓. Constraint is local — a running sum. Brute force is O(n²) — try every pair. Sliding window ✓.

Shape. Smallest-valid. As soon as the window's sum crosses target, we've found a valid window; the question is how much we can shrink from the left before it stops being valid. So we shrink while valid, measuring on each step.

State. A single integer: the running sum of the window.

def minSubArrayLen(target: int, nums: list[int]) -> int:
    left = 0
    total = 0
    best = float('inf')

    for right in range(len(nums)):
        total += nums[right]

        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1

    return 0 if best == float('inf') else best

Trace nums=[2,3,1,2,4,3], target=7. The window walks [2]→[2,3]→[2,3,1]→[2,3,1,2] (sum 8, valid), shrinks to [3,1,2] (sum 6, invalid), extends to [3,1,2,4] (sum 10, valid), shrinks to [1,2,4] (sum 7, valid), shrinks to [2,4] (sum 6, invalid), extends to [2,4,3] (sum 9, valid), shrinks to [4,3] (sum 7, valid). Best window seen: length 2.

The reason positive integers matter: total is monotonically non-decreasing in right and non-increasing in left. If they could be negative, this shrink rule would miss valid smaller windows on the other side of a dip — that's a different problem (prefix sums + hashmap territory).

Walkthrough 2 — LeetCode 3, Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring containing no repeated characters.

Recognition. Contiguous ✓. Longest ✓. Constraint is local — "does the character at right already live in the window?". Brute force is O(n²). Sliding window ✓.

Shape. Largest-valid. We extend until the window becomes invalid (a duplicate arrives), then shrink left until the duplicate is gone. Measure once per outer iteration, after the shrink.

State. A set of the characters currently in the window.

def lengthOfLongestSubstring(s: str) -> int:
    left = 0
    seen: set[str] = set()
    best = 0

    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        best = max(best, right - left + 1)

    return best

Trace s="abcabcbb". Windows: a, ab, abc, then s[3]='a' is in seen → shrink until a is gone: bc, then add: bca, add b: shrink until b is gone: cab, add c: shrink until c is gone: abc, then s[6]='b' in seen: shrink to cb, then s[7]='b': shrink to b, add — done. Best: 3.

A common speedup swaps the set for dict[char → last_seen_index], so left can jump directly past the previous occurrence in O(1) instead of shrinking char-by-char. Both are O(n); the dict version does fewer inner iterations but obscures the pattern. Master the set version first.

Walkthrough 3 — LeetCode 76, Minimum Window Substring

Given strings s and t, return the smallest substring of s containing every character of t (with multiplicity). Return "" if none exists.

This is the boss level. Every sliding-window interview eventually lands here, and it looks intimidating until you see it as LC 209 with a richer notion of "valid".

Recognition. Contiguous ✓. Shortest ✓. Constraint is local — "does the window contain enough of each required character?". Brute force is O(n² · |alphabet|). Sliding window ✓.

Shape. Smallest-valid, same as LC 209. Once the window contains all required characters, shrink from the left while it still does, measuring each step.

State. Two counters and one integer:

need: how many of each character t requires. Fixed.
window: how many of each character are currently in the window.
have: the number of distinct characters in need for which window[c] >= need[c]. When have == len(need), the window is valid.

have is the trick that makes this O(n) instead of O(n · |alphabet|). Without it, you'd re-check every character in need on every shrink step to decide validity. With it, validity is one integer comparison.

from collections import Counter, defaultdict

def minWindow(s: str, t: str) -> str:
    if not t or not s:
        return ""

    need = Counter(t)
    window: dict[str, int] = defaultdict(int)
    have = 0
    required = len(need)

    left = 0
    best = ""
    best_len = float('inf')

    for right in range(len(s)):
        c = s[right]
        window[c] += 1
        if c in need and window[c] == need[c]:
            have += 1

        while have == required:
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best = s[left:right + 1]

            drop = s[left]
            window[drop] -= 1
            if drop in need and window[drop] < need[drop]:
                have -= 1
            left += 1

    return best

The two "if c in need" guards are load-bearing. They ensure have only tracks characters we actually require — characters t doesn't ask for pass silently through both add and remove.

Trace s="ADOBECODEBANC", t="ABC". Three valid windows appear over the scan:

At right=5, the window is "ADOBEC" (length 6). Record it. Shrinking drops A and invalidates.
At right=10, A re-enters and the window s[1..10]="DOBECODEBA" is valid (length 10). Shrink D, O, B, E — all still valid — down to "CODEBA" (length 6). One more shrink drops C and invalidates. No improvement on best.
At right=12, C re-enters and the window s[6..12]="ODEBANC" is valid (length 7). Shrink O, D, E down to "BANC" (length 4). One more shrink drops B and invalidates.

Best: "BANC".

If you're new to this problem, don't just read the trace — run it by hand on paper with a five-column table: right, s[right], window, have, left. It's the fastest way to internalise why have only decrements when the window count drops below the requirement, not merely on any decrement.

When sliding window is not the tool

Same recognition checklist, but with the failure modes made explicit:

Non-contiguous. "Longest increasing subsequence" — the elements don't have to be adjacent. DP, not sliding window.
Two disjoint regions. "Best time to buy and sell stock" wants two indices with a gap, not a window. Linear scan with running min.
Negative numbers in a sum problem. Kills monotonicity; shrinking no longer preserves invariants. Reach for prefix sums + hashmap ("subarray sum equals K").
Global constraints. "Number of subarrays where the majority element appears ≥ k times" — you can't decide window validity in O(1). Different pattern (often prefix-sum with counting).

If you find yourself writing a while loop inside your while loop that scans the whole window on every step, you've broken the O(n) budget and the pattern is fighting you. Rethink state.

How the Algotrek tutor would prompt you here

When a learner opens a sliding-window problem on Algotrek, the adaptive tutor does not reveal the template. It asks three questions in sequence, and only advances when the learner can answer each in one sentence:

"What's the brute force, and where's the redundant work?" — Forces the learner to notice the O(n²) baseline and see that extending the window by one element reuses almost all the state of the previous window.
"Describe the window's validity in one sentence." — Forces state to be named. "Sum ≥ target." "No duplicate characters." "Window contains every character of t." If the learner can't say this cleanly, they're not ready to code.
"When the window becomes invalid, is there exactly one way to fix it?" — Forces the shrink rule to be named. This is where the largest-valid vs smallest-valid split gets learnt, not memorised.

Answer all three and the template writes itself — and, more importantly, transfers to LeetCode 424, LeetCode 567, LeetCode 1004, and every variable-window problem you'll see for the rest of your career.

That's the difference between grinding a pattern and internalising it. Try the Longest Substring Without Repeating Characters lesson on Algotrek to see the prompt-then-reveal flow in action on the flagship sliding-window problem.

Where to go next

LC 424, Longest Repeating Character Replacement. Same shape as LC 3, but the "valid" test now involves the count of the most frequent character in the window. A great test that you've understood state as the tunable knob.
LC 567, Permutation in String. Fixed-size variant with the LC 76 have-counter trick. Bridges the two flavours.
LC 1004, Max Consecutive Ones III. Largest-valid with a budget. Recognition is easy; the shrink rule is the interesting part.

If you can walk into any of those cold and write it in under 15 minutes, sliding window is yours. That's a real skill, and it composes: two-pointer, monotonic deque, and prefix-sum patterns all share the "extend right, contract left" bone structure. Learn this one deeply and the next three feel like variations.

For the O(n) claim in this post's opening — and every "amortised O(1) per element" argument the sliding-window pattern rests on — see the Big-O cheat sheet for the hash-map, set, and dynamic-array lines that make the collapse work.