Windows: Fixed vs Grow-and-Shrink

One idea, two flavors

A window is a contiguous chunk of an array or string, described by two indices: a left edge and a right edge. The sliding window pattern maintains that chunk while it moves across the input, updating some state (a sum, a character count) incrementally instead of recomputing from scratch. Done right, every element enters the window once and leaves once — linear work total.

The pattern comes in two flavors, and telling them apart is half the skill:

• Fixed size: the window is exactly k elements wide and slides one step at a time. For "subarray of size k" questions.
• Variable size (grow-and-shrink): the right edge expands greedily; the left edge advances only to repair the window when a rule breaks. For "longest/shortest subarray such that..." questions.

Fixed window: pay for the change, not the window

Say you want the maximum sum of any 3 consecutive elements of nums = [2, 5, 1, 8, 2, 9]. The naive way re-sums all 3 elements at each of the 4 positions — O(nk) work overall. But when the window slides one step right, only two things change: one element leaves on the left, one enters on the right. Subtract the leaver, add the enterer, done — O(1) per slide.

def max_window_sum(nums, k):
    if len(nums) < k:
        return 0                       # decide the n < k policy up front
    window = sum(nums[:k])
    best = window
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]   # enterer minus leaver
        best = max(best, window)
    return best

The index of the leaving element is the classic off-by-one: when nums[right] enters, nums[right - k] leaves (not right - k + 1). Check it with real numbers: at right = 3 with k = 3, the leaver is nums[0]. Correct.

The window state doesn't have to be a sum. For anagram problems (Permutation in String, Find All Anagrams), the window is exactly the pattern's length and the state is a letter-frequency map: increment the entering character, decrement the leaving one, and compare maps.

Variable window: expand right, repair left

Now a different question shape: longest substring without repeating characters in "abcabcbb". No fixed k — the window stretches. The rhythm:

1. The right edge advances one step every iteration, adding its character to the window state.
2. If the window now breaks the rule (a duplicate appeared), advance the left edge — removing characters from the state — until the window is valid again.
3. Once valid, record right - left + 1 against the best.

On "abcabcbb": the window grows to "abc" (length 3). The next 'a' is a duplicate, so the left edge slides past the old 'a', giving "bca". Every later character repeats the same dance — grow one, shed until clean — and the best never beats 3.

def longest_no_repeat(s):
    seen = set()
    left = 0
    best = 0
    for right in range(len(s)):
        while s[right] in seen:        # invalid: repair from the left
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        best = max(best, right - left + 1)   # update only when valid
    return best

Despite the nested while, this is O(n): both pointers only move forward, so across the whole run each element is added once and removed at most once — at most 2n pointer moves total.

Longest vs shortest: where the answer update lives

Grow-and-shrink itself has two sub-flavors, and they differ in exactly one place — where the best-so-far update sits relative to the shrink loop:

Mixing these up is the most common template bug. For "longest", updating before restoring validity records illegal windows. For "shortest", you deliberately shrink while the window still works, recording each smaller success — the last recorded length before the requirement breaks is that right edge's best.

The fine print: the condition must be monotone

Shrinking is only safe when the window condition is monotone: growing the window never fixes a violation, and shrinking never creates one. That's what justifies never moving a pointer backward.

With all-positive numbers and a sum condition, this holds: adding elements only raises the sum, removing only lowers it. Add negatives and it shatters. Try "shortest subarray with sum ≥ 5" on [3, −2, 6]:

• Grow to [3, −2, 6]: sum 7 ≥ 5 → record length 3, then shrink.
• Drop the 3: [−2, 6] has sum 4 < 5 → stop. Answer reported: 3.
• True answer: [6] alone, length 1. The window walked right past it.

The shrink stopped early because removing an element raised nothing — but a further shrink would have removed the −2 and brought the sum back up. Monotonicity is broken, so the "each pointer only moves forward" logic silently returns wrong answers. For sum targets with negatives, the right tools are prefix sums with a hash map (exact sum) or a monotonic deque (sum ≥ K).

Recognition signals

• "Subarray/substring of size k", "every window of length k" → fixed window.
• "Longest substring such that ⟨condition⟩", "at most K distinct" → grow-and-shrink, longest flavor.
• "Smallest/minimum window containing...", "shortest subarray with sum ≥ target" (positives only) → grow-and-shrink, shortest flavor.
• "Maximum of every window" → sliding window plus a monotonic deque (next lessons).
• Sum condition with negative numbers → not this pattern; reach for prefix sums.

Pitfalls checklist

1. Recomputing the whole window per slide — O(nk) instead of O(n).
2. The leaver is a[right - k], and the input may have fewer than k elements.
3. Longest vs shortest template mix-up — the answer update's position is the whole difference.
4. Updating state asymmetrically: whatever the add does, the remove must undo exactly.
5. Trusting the pattern without checking the condition is monotone.