Variable-Size (Flexible) Sliding Window

What problem this solves

Fixed-Size Sliding Window handles the case where k is handed to you. Most real interview problems are less generous: they ask for the longest substring satisfying some property, or the shortest subarray meeting some threshold — the window size is not an input, it's the output. Brute force means checking O(n²) start/end pairs (and, if evaluating each pair costs O(n), O(n³) overall). The variable-size sliding window collapses this to O(n) by growing the window greedily on the right and shrinking it on the left only when a correctness invariant is violated, reusing all the incremental state from the previous position instead of re-scanning.

How to recognize it in a problem statement

• "Longest/shortest contiguous subarray/substring such that <condition>" — the word "contiguous" is the tell; if the problem allows non-contiguous selection, you're likely looking at Dynamic Programming or a hash-map counting trick instead (e.g. "subarray sum equals k" with negative numbers is a prefix-sum + hash map problem, not sliding window, because a growing window's sum isn't monotonic when negatives are allowed).
• A monotonic "badness" condition: as the window grows, some property can only get worse (more distinct characters, more replacements needed, sum only increases because all values are non-negative). This monotonicity is what guarantees the left pointer never needs to move backward.
• Two flavors show up almost every time: maximize the window subject to "stays valid" (longest substring with at most K distinct characters), or minimize the window subject to "becomes valid" (shortest subarray whose sum is at least a target).

Mechanics: expand, then shrink-while-invalid

Unlike the fixed-size template, the shrink step here is a while loop, not a conditional — a single character/element entering the window can require the left pointer to jump multiple positions to restore validity.

The two flavors differ only in where you record the answer and what "invalid" means:

• Longest-with-condition (e.g. "at most K distinct characters"): the while loop's condition is "window currently violates the constraint" (distinct count > K). You update best after the shrink loop, when the window is guaranteed valid again — you're looking for the longest valid window.
• Shortest-with-condition (e.g. "sum >= target"): the while loop's condition is "window currently satisfies the constraint" (sum >= target), and you shrink as far as possible while it still holds, updating best inside the loop on every valid state, because you want the smallest window that still works, and shrinking further might still be valid.

The at-most-K vs. exactly-K trick

A frequent interview curveball: "find the number of subarrays with exactly K distinct integers." A single sliding window can't track "exactly K" directly, because validity isn't monotonic in a way a simple two-pointer window can maintain (both growing and shrinking can move you into or out of exactly-K). The standard resolution is the subtraction trick:

exactly(K) = atMost(K) - atMost(K - 1)

You write one clean, monotonic helper — atMost(K): count subarrays with at most K distinct values, using the standard shrink-while-invalid window — and call it twice. This works because "at most K" is monotonic (adding elements can only keep distinct-count the same or increase it), so the helper is a straightforward application of the longest-with-condition template, just counting right - left + 1 valid subarrays ending at right instead of tracking a max length. This trick generalizes: any "exactly K" counting problem where "at most K" is easy to compute is a candidate for this subtraction.

Other recurring variations

Variation	Window state	Shrink condition
At-most-K distinct	Hash map of value → count, plus len(map)	len(map) > K
Sum-based threshold (non-negative values only)	Running sum	sum >= target (shrink to minimize) or sum > target (shrink to stay valid)
Character-replacement budget	Frequency array + running max frequency in window	(window length - max frequency) > k
Two-basket / at-most-2-types	Hash map of value → count	len(map) > 2
Anagram/permutation coverage	Two frequency maps + a "satisfied count"	Not this shape — this is actually the fixed-size pattern, since the target length is fixed

Complexity analysis

• Time: O(n) amortized, not O(n²), even though there's a while loop nested inside a for loop. The argument: right advances exactly n times total, and left also advances at most n times total across the entire run (it only ever moves forward, never resets). So the combined work done by all iterations of the inner while loop, summed across the whole outer loop, is bounded by n, not n per outer iteration. This is the amortized analysis you first saw in Big-O & Complexity Analysis, applied concretely: the "nested loop that looks like O(n²)" is actually O(n) because the total number of pointer movements, not the loop nesting, is what bounds the work.
• Space: O(1) for a running sum/count; O(min(n, alphabet size)) for a frequency map over a bounded alphabet; O(n) if the window state is a hash map keyed by arbitrary values with no bound on distinct keys.

Pitfalls and interview gotchas

• Assuming non-monotonicity away. The sum-based variant only works because all values are non-negative (or all the same sign) — with negative numbers, growing the window doesn't monotonically increase the sum, so shrinking it doesn't have a reliable stopping rule. If you see negative numbers and a "subarray sum" ask, pivot to prefix sums + hash map (Arrays & Hashing topic), not sliding window.
• Off-by-one when computing the window length. It's right - left + 1, not right - left — a classic silent-failure bug that under-counts by one for every window.
• Updating best in the wrong place. For "shortest valid window" problems, you must update the answer inside the shrink loop (every time the window is still valid, before it becomes invalid again), not just once after the loop exits — otherwise you'll only ever record the last valid state you shrunk to, not the best one seen along the way.
• Forgetting to undo state on shrink. Every add needs a symmetric remove; if your frequency map only increments and never decrements as left advances, the window's state silently drifts out of sync with its actual contents.
• The "at most K" helper double-counting or under-counting. When counting subarrays (not just tracking a max/min length), the number of new valid subarrays added at each step is right - left + 1 (all subarrays ending at right starting anywhere from left to right), not 1. This is the detail that makes or breaks the at-most-K vs. exactly-K trick.
• Confusing "window is currently invalid" with "window was just invalidated by the last add." Some implementations reset an entire counter and rescan instead of doing an O(1) incremental check — this is correct but silently degrades your complexity back toward O(n · window size).

Fixed-size vs. variable-size at a glance

	Fixed-size	Variable-size
Window length	Given (k)	Discovered; the answer itself
Shrink trigger	Every step, once window reaches size k	Only when the invariant breaks (0+ times per step)
Loop shape	for + if	for + inner while
Answer recorded	Once per full window	After shrink loop (longest) or inside it (shortest)

A worked pattern (not one of your assigned problems)

To see the shrink-while-invalid mechanic without touching your assigned problems, consider a made-up variant: given an array of positive integers and a cap C, find the length of the longest subarray whose product is strictly less than C.

Every element is multiplied in once (right) and divided out at most once (left), so the whole scan is O(n) despite the nested loop — the same amortized argument as before, just with a product instead of a sum or a frequency map.

Where this connects

This is the more general sibling of Fixed-Size Sliding Window, and both are specializations of the same-direction two-pointer discipline from the Two Pointers topic — the pointers here never cross and never move backward, they just grow and shrink a live window instead of converging from opposite ends. When the "shrink" logic needs to track a running maximum efficiently rather than a sum or frequency count, you're often one step away from needing a monotonic structure, which is exactly where the upcoming Monotonic Stack topic picks up.