The Sliding Window Pattern

The tell: when does this pattern apply?

You are staring at a problem. Something about it feels like it wants nested loops. Before you write them, check for three things:

1. The input is a linear sequence — an array or a string.
2. The answer is about a contiguous subarray or substring (not arbitrary subsets).
3. The objective is "longest", "shortest", "minimum", "maximum", "exactly k", or "contains all of X".

If all three are true, try sliding window before anything else. The brute force for these problems almost always looks like:

for i in range(n):
    for j in range(i, n):
        # check window arr[i..j]

That inner loop is doing redundant work. When i advances from 3 to 4, most of the window arr[3..j] overlaps with arr[4..j]. The sliding window keeps that overlap alive and only processes the new element and the dropped element.

Fixed window: the easy case first

Fixed window problems give you the window size k upfront. "Maximum sum of any k consecutive elements" is the canonical one. The brute force recomputes the sum of each window from scratch — O(n·k). The insight: when you slide the window one step right, the new sum is just the old sum plus the incoming element minus the outgoing one.

def max_sum_fixed(arr, k):
    if len(arr) < k:
        return None

    # Build the first window
    window_sum = sum(arr[:k])
    best = window_sum

    # Slide: add the new right element, subtract the element leaving on the left
    for right in range(k, len(arr)):
        window_sum += arr[right]          # expand right
        window_sum -= arr[right - k]      # shrink left (the element k steps behind)
        best = max(best, window_sum)

    return best

One pass, O(n), O(1) extra space. The key move — arr[right - k] is exactly the element that just fell off the left edge when the window advanced.

Fixed windows are almost too simple once you see it. The interesting problems are variable.

Variable window: expand right, shrink left

Most interview sliding window problems do not give you k. Instead they give you a constraint and ask you to find the optimal window that satisfies it. The window has to breathe.

The template is worth memorizing:

def variable_window(arr):
    left = 0
    state = ...          # running sum, counter dict, set, etc.
    best = 0

    for right in range(len(arr)):
        # 1. Expand: include arr[right] in the window
        state = update(state, arr[right])

        # 2. Shrink: while the constraint is violated, drop the left element
        while invariant_violated(state):
            state = remove(state, arr[left])
            left += 1

        # 3. The window [left, right] now satisfies the constraint.
        #    Update the answer.
        best = max(best, right - left + 1)

    return best

The reason this is O(n) and not O(n²): each element is added to the window exactly once (when right passes over it) and removed at most once (when left catches up). Two total operations per element across the entire run — O(n) total, regardless of how many times the inner while fires.

Let's make that concrete with two real problems.

Worked problem 1: longest substring without repeating characters

Problem: Given a string, find the length of the longest substring that contains no duplicate characters.

The brute force checks all O(n²) substrings and scans each for duplicates — O(n³) total. Variable window gets it to O(n).

Invariant: the window s[left..right] contains no character more than once.

State: a set of the characters currently inside the window.

def length_of_longest_substring(s: str) -> int:
    seen = set()       # characters in the current window
    left = 0
    best = 0

    for right in range(len(s)):
        # Shrink from the left until the new character fits
        while s[right] in seen:
            seen.remove(s[left])
            left += 1

        seen.add(s[right])
        best = max(best, right - left + 1)

    return best

Walk through "abcabcbb":

• right=0 ('a'): seen={a}, window="a", best=1
• right=1 ('b'): seen={a,b}, window="ab", best=2
• right=2 ('c'): seen={a,b,c}, window="abc", best=3
• right=3 ('a'): 'a' is in seen — shrink. Remove 'a', left=1. Now 'a' not in seen. Add 'a', seen={b,c,a}, window="bca", best=3
• right=4 ('b'): 'b' is in seen — shrink. Remove 'b', left=2. Add 'b', window="cab", best=3
• ... and so on.

The answer is 3 ("abc"). Notice the while loop: when you hit a repeat, you keep shrinking — not just once. That while-not-just-if distinction is where most bugs hide.

{ "type": "array", "title": "longest substring: track [left, right] as the window slides", "data": [1, 2, 3, 1, 2, 3, 2, 2] }

Play with this. Imagine each element is a character. When a duplicate enters from the right, left has to chase it down — and it might have to move more than one step.

Worked problem 2: minimum window substring (sketch)

This one is a classic hard problem that still reduces to the same template. Given a string s and a pattern t, find the smallest substring of s that contains all characters of t (including duplicates).

The constraint is now more complex — not just "no repeats" but "contains the full frequency map of t." The state becomes a frequency counter, and you track how many distinct characters are currently satisfied.

from collections import Counter

def min_window(s: str, t: str) -> str:
    need = Counter(t)       # how many of each char we still need
    missing = len(t)        # total characters still owed to the window
    best_start, best_len = 0, float('inf')
    left = 0

    for right, c in enumerate(s):
        # Expand: if this character helps satisfy the constraint, decrement missing
        if need[c] > 0:
            missing -= 1
        need[c] -= 1        # note: need[c] can go negative (we have surplus)

        # Shrink: once the constraint is met, try to tighten the left
        if missing == 0:
            # Move left as far as possible while still satisfying the constraint
            while need[s[left]] < 0:
                need[s[left]] += 1
                left += 1

            # Record this window
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_start = left

            # Shrink one more step to break the constraint and keep searching
            need[s[left]] += 1
            missing += 1
            left += 1

    return s[best_start : best_start + best_len] if best_len < float('inf') else ""

The structure is identical: expand right, check constraint, shrink left, record the best. The sophistication is in how you track the constraint — here a counter and a missing tally. Once you can read "expand right / shrink left / maintain invariant," you can adapt this skeleton to almost anything.

The complexity picture

Approach	Time	Space	When
Brute force (nested loops)	O(n²) or O(n·k)	O(1)	Never, unless n < 100
Fixed sliding window	O(n)	O(1)	Window size k is given
Variable sliding window	O(n)	O(k)	Optimal size is part of the answer
Variable + hash map	O(n)	O(∣Σ∣)	Constraint involves character/element counts

The space O(∣Σ∣) for the hash-map variants is bounded by the alphabet or the set of distinct values — for ASCII strings that is at most 128, effectively constant.

Compare the brute force and the variable window on the same input of n=10,000:

• Brute force: ~50 million operations.
• Sliding window: ~20,000 operations (two passes over 10,000 elements).

That is a 2500x speedup from one insight.

The classic bug: forgetting to shrink

Here is a broken version of the longest-substring solution:

def broken_longest_substring(s: str) -> int:
    seen = set()
    left = 0
    best = 0

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

    return best

The if instead of while only removes one character from the left when a duplicate appears. But what if the duplicate character is not the immediate left element? On "abba":

• right=3 ('a'): 'a' is in seen (from index 0). We remove s[left] = 'a', left=1. Now seen={'b','b'} — wait, 'b' appears twice, we have a second problem. The window seen is now corrupted.

The fix is always while: keep removing from the left until the invariant actually holds, not just until you've done one removal. The invariant has to be true when you exit the shrink phase, and a single removal does not guarantee that.

Run this mentally on any example where the new right element is not adjacent to its previous occurrence. The if version will give you wrong answers every time.

When sliding window is the wrong tool

Sliding window requires that you can add and remove elements from the window state cheaply and that moving a pointer in one direction is always correct (no backtracking).

Skip it when:

• The subarray does not have to be contiguous. Non-contiguous subsets → dynamic programming or backtracking.
• The answer involves pairs or triplets that are not neighbors. Sounds like two pointers or sorting.
• The constraint is non-monotonic — adding more elements can both satisfy and violate it. Classic example: "subarray with sum exactly k where elements can be negative." With negative numbers, a larger window is not necessarily worse, so you cannot decide greedily whether to shrink. Prefix sums and a hash map handle that case.
• The data is 2D. You need extra machinery (collapse rows with prefix sums, then slide).

The monotonicity check is the most important: ask yourself "if the current window violates the constraint, does extending it further help or hurt?" If extending always hurts, shrinking from the left is safe and sliding window applies. If extending might help (negative numbers, for instance), it does not.

Patterns this unlocks

Once the template is in your head, a surprising number of problems click:

• Max sum of k elements — fixed window, running sum.
• Longest substring without repeating characters — variable window, set.
• Minimum window substring — variable window, frequency counter.
• Fruits into baskets / at most K distinct — variable window, counter with distinct-key tracking.
• Longest subarray with ones after replacing at most k zeros — variable window, count of zeros in window.
• Permutation in string — fixed window of length len(p), frequency counter comparison.

Every one of these is the same skeleton with a different invariant slotted in. That is the power of pattern recognition — you are not solving 10 different problems, you are solving one problem with 10 different constraints.

For problems where the window needs a max or min of the elements inside it (not just a sum), the window alone is not enough — pair it with a monotonic deque. But that is a technique for another day.

Putting it together

The next time you hit a problem that says "longest", "shortest", "minimum", or "maximum" over a contiguous range, do this:

1. Identify the invariant — what property must the window always satisfy?
2. Choose your state — sum, set, counter, whatever tracks that invariant cheaply.
3. Write the template: for right in range(n) → expand → while violated → shrink → record.
4. Check: is every element added once and removed at most once? If yes, you have O(n).

That is it. The sliding window is not a clever trick so much as a disciplined way of not redoing work. Once you see it, you cannot unsee it — and you will see it everywhere.

For related techniques, two pointers solves a similar class of problems but with pointers moving from both ends toward the middle rather than a window moving in one direction. For the hash map and set internals used to maintain window state, see hash table. And if you are still fuzzy on why O(n) beats O(n²) by so much in practice, Big-O has the concrete numbers.