Sliding window: the prerequisite nobody mentions

Most write-ups of the sliding window open with the template: two pointers, a loop, expand the right, shrink the left. I want to do the opposite, because the template was never my problem. I could write it. What I couldn't do was tell when it was allowed, and that's the gap that produced wrong answers I didn't notice. This is a sibling to the DP post: the pattern only sticks once you can prove why the cheap move is safe.

When is a window even legal?

Here's the move underneath every window: you have a contiguous run of elements, and you decide whether to extend it or contract it based on some quantity measured over the run. The whole technique rests on one assumption — that as you add elements, that quantity moves in a single, predictable direction.

Call it the monotonicity prerequisite. If growing the window only ever pushes the tracked quantity up (or only ever down), then when the window violates your constraint you know unambiguously what to do: shrink. And when it satisfies the constraint, you know growing is what might break it. There's no ambiguity about which way to move because the quantity can't double back on you.

The cleanest example: the sum of a window of non-negative numbers. Add an element, the sum can only stay the same or rise. So "smallest window whose sum is at least k" is decidable — if the sum is too big, dropping the leftmost element is the only sensible move, and dropping it can only lower the sum toward the target. The window never lies to you about direction.

Now break it. Allow negative numbers. Adding an element might lower the sum. Now when your window's sum overshoots, shrinking from the left might raise it, or lower it further — you genuinely cannot tell. The signal that told you which way to move is gone. This is the exact reason a windowed approach fails on problems that look windowed but aren't, and it's why Kadane and a whole class of prefix-sum problems can't use a window: their quantity isn't monotonic in window growth, so there's no valid shrink decision to make.

Exact-equality targets break it the same way for a different reason. "A window summing to at least k" has a direction; "a window summing to exactly k" does not — overshooting and undershooting both push you away, and there's no monotone boundary to ride. That's a prefix-sum-with-a-hashmap problem wearing a window costume.

So the prerequisite, stated as a check you run first: the constraint must have a monotone boundary in window size — a point past which growing always violates and shrinking always recovers. Earn that, and the rest is mechanics.

The fork: if versus while

Once a window is legal, there are exactly two shapes, and the difference between them is one keyword.

A fixed window has a known size k. You add the incoming element, and the moment the window exceeds size k you remove exactly one element from the back. One in, one out. That "remove one" is an if — a single gate that fires at most once per step, because you only ever overshoot the size by one.

A variable window has no fixed size; it's bounded by a constraint. You add the incoming element, then you shrink as long as the constraint is violated. That's a while — you might have to drop several elements to get back to a valid window, or none at all.

The bug I want to flag here is subtle and I made it: in a fixed-window problem, checking the constraint outside the size gate. You compute your window statistic before the window has reached size k, so you're comparing a half-built window against the answer. The fix is to evaluate the constraint only once the if has trimmed the window back to exactly k. Same family as == versus >= slips on the boundary — off-by-one in when you look, not where you point.

The need counter: one integer instead of a fragile map

The single biggest unlock for me on variable windows was a way to represent "is this window valid?" without scanning anything.

Naively, when a window has to contain certain characters with certain multiplicities, you keep a frequency map of what you still owe and ask, every step, "is the map all satisfied?" That check is fragile and not free — you're inspecting whether every entry has been driven to zero or below. I kept getting the all-satisfied condition subtly wrong.

Replace the whole thing with one integer, need — the count of requirements not yet met. The window is valid exactly when need == 0. The art is in maintaining it, and it comes down to a single observation that took me a while to actually believe.

When you add a character, you've reduced the deficit for that character by one. But you should only decrement need if that character just crossed from owed to settled — the moment its deficit hits exactly zero. When you remove a character, you've increased its deficit by one, and you should only increment need if it just crossed from settled to owed — the moment its deficit goes from zero to below zero.

The reason it's only the crossing — and this is the heart of the whole post — is that every other add and remove happens while the character was already in surplus or already in deficit. If I'm adding a character I already have more than enough of, my satisfaction count doesn't change; it was satisfied before and it's satisfied after. The only event that can change the count of unmet requirements is the one transition that flips a single requirement's status. Everything else is noise to need. So I don't recount anything; I watch one boundary per character and adjust by one.

Here's the maintenance, isolated. count holds the running deficit per character (positive means still owed); need is the scalar.

// adding c into the window
count[c, default: 0] -= 1
if count[c] == 0 { need -= 1 }   // just settled: crossed owed -> 0

// removing c from the window
count[c, default: 0] += 1
if count[c] == 1 { need += 1 }   // just unsettled: crossed 0 -> owed

The asymmetric-looking constants (== 0 on the way in, == 1 on the way out) are the same boundary seen from two sides — 0 is where the deficit lands when entering, 1 is the first value it takes after leaving. need == 0 is now the entire validity test, evaluated in constant time, with no map scan and nothing fragile to get wrong.

Record placement: the min/max switch

Here is the distinction that silently decides correctness on half of all window problems, and the one where I burned the most time. With the same loop body — same expand, same shrink, same validity test — where you record the answer relative to the shrink loop determines whether you find the smallest valid window or the largest.

1. Recording inside the shrink loop
   You shrink while the window is valid, and you record the answer after each successful shrink. You're capturing the window at its tightest valid configuration, which gives you the minimum valid window.
2. Recording after the shrink loop
   You shrink only until the window becomes valid, then exit the loop and record once. You're capturing the window at its largest extent under the constraint, which gives you the maximum valid window.

I repeatedly put the answer-tracking in the wrong spot — recording the max inside the shrinking phase when it belonged after it, and the reverse. It's the canonical record-placement bug: identical loop, answer in the wrong place, no crash, no error, just a quietly incorrect result. It's worth dramatizing precisely because nothing tells you. The compiler is happy. Small tests can pass. You find out from a case you didn't write.

The cautionary case: smallest window covering a target

The problem that pulled all three ideas together: find the shortest substring of a string s that contains every character of a target t, counting multiplicity. It needs the need counter for validity, and it's a minimum-window problem, so the answer is recorded inside the shrink loop.

I got the logic right and still wrote a quadratic solution without noticing. My instinct for "track the best answer so far" was to construct the substring every time I found a smaller valid window and hold onto the string itself. Building a substring is linear in its length, and doing that inside the sweep turns an O(n) algorithm into O(n^2). It timed out.

The fix is small and it's a habit worth internalizing: don't store the answer, store the boundaries. Keep the start and end indices of the best window as two integers, and slice the string exactly once at the very end. The sweep stays linear because recording an answer is now two assignments, not a string build.

The template, last

Now that it's earned, here's the variable-minimum-window skeleton. Every piece in it is something we derived: the legality check is assumed satisfied, need is the validity scalar, the shrink is a while, and the answer is recorded inside that while because we want the minimum.

var left = 0
var bestStart = 0, bestLen = Int.max
for right in s.indices {
    // expand: add s[right], maintaining `need` at its boundary crossing
    while need == 0 {                       // window valid -> tighten it
        let len = s.distance(from: left, to: right) + 1
        if len < bestLen { bestLen = len; bestStart = left }  // record INSIDE: minimum
        // remove s[left], maintaining `need`, then advance left
    }
}

For a maximum-window variant, the shape inverts: the while shrinks only until the constraint is restored, and the recording moves below the loop. Same parts, one switch flipped — which is exactly why getting the switch wrong is so easy and so quiet.

This is the anchor for the rest of the series; when two pointers, prefix sum, and Kadane point back to "monotonicity decides whether a sweep is legal," this is the argument they mean.

Problems to practice