The Sliding Window

A sliding window is a two-pointer pattern specialized for contiguous subarrays and substrings. Instead of two pointers converging from the ends, both pointers move left-to-right: a right pointer grows the window by admitting new elements, and a left pointer shrinks it whenever the window breaks a rule.

The canonical example: find the length of the longest substring with no repeating characters. Watch the window stretch as long as characters stay unique, then snap forward the moment a duplicate appears.

Follow the pointers. The right pointer marches forward one character at a time. The instant it admits a character already inside the window, the left pointer jumps just past the earlier copy, restoring the “no repeats” invariant. The window never travels backward, so although it looks like nested movement, each pointer only advances — that’s the O(n) magic.

The invariant is the whole game

Every sliding-window problem is defined by an invariant — a condition the window must always satisfy:

• No repeated characters → shrink when a duplicate enters.
• Sum ≤ budget → shrink while the sum is too large.
• At most k distinct values → shrink when a (k+1)ᵗʰ distinct value enters.

Your job is to identify the invariant, then answer two questions: when do I grow? (usually every step) and when must I shrink? (whenever the invariant is violated).

def longest_unique(s):
    seen = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1      # shrink past the duplicate
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

Fixed vs. variable windows

There are two flavors:

• Fixed-size window — the window is always exactly k wide (e.g. “maximum sum of any k consecutive elements”). You add the new element and remove the one falling off the back in O(1).
• Variable-size window — the width flexes to keep the invariant true, like the example above. This is the more common and more powerful form.

When to reach for it

Reach for a sliding window when the problem asks about a contiguous run — “subarray,” “substring,” “consecutive” — and you want the longest, shortest, or some aggregate over it. If the elements don’t have to be contiguous, a window won’t help; you’re likely looking at sorting, hashing, or dynamic programming instead.

Watch for the word contiguous. It is the signal that separates a sliding window from a subsequence problem.

Pattern recognition

Variations

Worked problems

The invariant is different in each one: best buy price, unique characters, and a minimum sum threshold.

def max_profit(prices):
    min_price = float("inf")
    best = 0

    for price in prices:
        best = max(best, price - min_price)
        min_price = min(min_price, price)

    return best

def length_of_longest_substring(s):
    last_seen = {}
    left = 0
    best = 0

    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1

        last_seen[ch] = right
        best = max(best, right - left + 1)

    return best

def min_sub_array_len(target, nums):
    left = 0
    total = 0
    best = float("inf")

    for right, x in enumerate(nums):
        total += x

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

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