The sliding window: recognising when it applies

Most explanations of the sliding window give you three solved problems and hope the pattern rubs off. It rarely does. You finish able to recite the code for "longest substring without repeating characters" and still stall on the next problem, because what you were never taught is the thing that actually matters: how to look at an unfamiliar question and recognise that a window applies.

So this is mostly about recognition. The code is short and there is not much of it — two shapes, really. The hard part is knowing when to reach for them, and that comes from understanding what the technique exploits rather than what it looks like.

The waste that the technique removes

Start with a concrete problem and the obvious solution. Given a list of numbers and a size k, find the largest sum of any k consecutive elements.

def max_sum_brute(nums, k):    best = None    for i in range(len(nums) - k + 1):        total = sum(nums[i:i + k])      # re-adds k elements every time        if best is None or total > best:            best = total    return best

That is correct, and it is O(n * k). Now look at what it repeats. Moving from the window starting at index 3 to the one starting at index 4, k-1 of the elements are the same elements. The code throws that away and re-adds all k from scratch.

The fix follows directly from naming the waste. Consecutive windows overlap, so instead of recomputing, adjust: add the element entering on the right, subtract the one leaving on the left.

def max_sum_k(nums, k):    if k <= 0 or len(nums) < k:        return None    window = sum(nums[:k])              # first window, once    best = window    for right in range(k, len(nums)):        window += nums[right] - nums[right - k]        best = max(best, window)    return best

One pass, O(n), and k has vanished from the complexity entirely. Checked against a few inputs including the awkward ones:

[2, 1, 5, 1, 3, 2] k=3 -> 9[5]                k=1 -> 5[1, 2]             k=5 -> None      # window larger than the input[-3, -1, -4, -1]   k=2 -> -4        # all negative: still correct[4, 4, 4, 4]       k=2 -> 8

That reuse of the overlap is the entire pattern. Everything else in this article is bookkeeping around that one idea. If you remember nothing else, remember that a sliding window is what you get when you notice that consecutive candidate answers share almost all of their input.

Deciding whether a window applies

Three conditions have to hold. Check them in order, and be strict about the first.

The answer is a contiguous run. A subarray or a substring — elements adjacent in the original order. This is the condition people misread, because it is easy to skim a problem about "a selection of elements" and start reaching for a window. If the elements may be non-adjacent, that is a subsequence, and a window cannot help: the window's whole premise is that leaving one end drops exactly the elements you passed.

You want an extreme or a count. Longest, shortest, maximum, minimum, how many, or does one exist. A window walks candidates in order and keeps the best, so the question has to be answerable that way.

The constraint behaves monotonically. Growing the window must push the condition one way and shrinking it the other. "At most two distinct characters" qualifies: adding an element can only maintain or break it, removing can only maintain or restore it. That property is what makes it safe to move the left edge forward and never go back.

Now a problem that looks like a window and is not: find the maximum sum of any k elements. Contiguous run? No — you may take any k elements. Sort descending and take the first k; there is no window here at all. Change one word to "any k consecutive elements" and it becomes the problem we just solved. That single word is doing all the work, and reading for it is the skill.

A second, subtler failure: the longest subarray whose product is under a limit, where the array may contain negatives. Contiguous, asks for longest, sounds ideal. But a negative number can make the product jump from too large to acceptable and back, so the constraint is not monotonic. Shrinking from the left is no longer guaranteed to move you toward validity, and the technique breaks. With all-positive values it works fine. The lesson: verify monotonicity against the actual data, not against the shape of the sentence.

The fixed window

When the size is given, the loop is mechanical: add the entering element, remove the leaving one, record the answer. There is no decision to make, which is why fixed windows are worth recognising instantly — they are the easy case, and the only real risk is an off-by-one in the initial fill or the loop bounds.

Note in max_sum_k above that the first window is built before the loop, and the loop starts at k rather than 0. Getting this wrong by one is the most common bug in fixed-window code, and it usually produces a plausible answer rather than a crash, which is what makes it dangerous. Test with a window equal to the array length, and a window larger than it.

The variable window, and why two loops are still linear

The interesting case is when the size is not given and you have to find it. The shape: expand the right edge greedily; whenever the window becomes invalid, contract from the left until it is valid again.

Take the longest substring with no repeated character. Tracking each character's most recent position lets the left edge jump rather than crawl:

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

The last[ch] >= left test matters: a repeat that sits behind the current left edge is not in the window and must be ignored. Dropping that condition is a real bug that passes casual testing.

'abcabcbb' -> 3'bbbbb'    -> 1'pwwkew'   -> 3''         -> 0'abcdef'   -> 6

Now the part that trips almost everyone. The general variable-window solution has a while inside a for, which looks quadratic. It is O(n), and the reason is worth stating precisely because it recurs across many techniques.

Count total work rather than nesting depth. The right pointer advances exactly n times. The left pointer only ever advances, never retreats, so across the entire run it also moves at most n times. Every element therefore enters the window once and leaves at most once — at most 2n pointer movements in total, regardless of how they are distributed between the loops. The inner loop might run five times on one iteration and zero times on the next twenty; what is bounded is the sum, not the per-iteration count.

Once that argument is internalised, a whole family of two-pointer solutions stops looking suspicious.

Tracking the constraint in constant time

The harder variable-window problems need one more idea. Consider: find the shortest substring of s containing all characters of t, including duplicates.

The naive approach rechecks "does the window contain everything needed" after every move, which is O(alphabet) per step and buries the linear-time win. The trick is to maintain a single integer counting how many requirements are currently unmet, and update it only at the moments it can change:

from collections import Counterdef min_window(s, t):    if not t or not s:        return ""    need = Counter(t)    missing = len(need)        # how many distinct chars are still short    have = Counter()    left = 0    best = (float("inf"), 0, 0)    for right, ch in enumerate(s):        if ch in need:            have[ch] += 1            if have[ch] == need[ch]:      # exactly satisfied, not over                missing -= 1        while missing == 0:               # valid: try to shrink            if right - left + 1 < best[0]:                best = (right - left + 1, left, right)            c = s[left]            if c in need:                if have[c] == need[c]:    # about to break it                    missing += 1                have[c] -= 1            left += 1    return "" if best[0] == float("inf") else s[best[1]:best[2] + 1]

The two == comparisons are the load-bearing lines. missing decreases only when a count reaches its requirement exactly — not when it exceeds it, or a character appearing five times when two are needed would be counted three times over. Symmetrically, missing increases only when removing a character takes it from exactly-enough to not-enough. Getting either of these to a >= silently breaks the answer.

s='ADOBECODEBANC' t='ABC' -> 'BANC's='a'             t='a'   -> 'a's='a'             t='aa'  -> ''      # not enough copiess=''              t='A'   -> ''s='ab'            t='b'   -> 'b'

Note the t='aa' case. A solution tracking only which distinct characters are present returns 'a' here, which is wrong. Duplicate requirements are where most implementations of this problem fail, and it is worth testing deliberately.

The bugs you will actually write

Four of them, in rough order of how often they appear.

Recording the answer at the wrong moment. For a longest-window problem, record after restoring validity; for a shortest-window problem, record while the window is valid, before shrinking further. Reversing these gives answers that are right on simple inputs and wrong on the interesting ones — the worst kind of bug, because casual testing endorses it.

Off-by-one in the window length. It is right - left + 1 when both ends are inclusive. Write it out once, convince yourself with a two-element example, and stop rederiving it under pressure.

Forgetting to shrink at all. Expanding without ever contracting is just a prefix scan wearing a window's clothes. If left never changes, you have not written a window.

Unhandled degenerate input. Empty collection, k of zero, k larger than the input, a target longer than the source. These are one-line guards and they are the cases a reviewer will try first.

Practising the recognition

Read each of these and decide whether a window applies before looking at the verdict. That decision is the skill; the implementation is comparatively mechanical.

• Longest substring with at most two distinct characters. Yes — contiguous, asks longest, and the distinct count moves monotonically as the window grows and shrinks.
• Does any pair in the array sum to a target? No. The pair need not be adjacent. That is a hash set in one pass, or two pointers on a sorted array — related, but not a window.
• Maximum average of any k consecutive readings. Yes, and it is the fixed-window sum divided by k. Do not divide inside the loop.
• Shortest subarray whose sum is at least a target, all values positive. Yes — the positivity is what supplies monotonicity, and the problem is unrecognisable as a window without it.
• Count subarrays with exactly k distinct values. Yes, but not directly: "exactly k" is not monotonic. Compute at-most-k minus at-most-(k-1), each of which is a clean window. Worth knowing, because a decomposition like this is often the answer when the constraint fails the monotonicity test.

If you can run those five judgements confidently, you will handle the sixth problem you have never seen, which is the whole point. The two code shapes take an afternoon to memorise and are worth very little on their own.