Sliding Window (Fixed and Variable)

Sliding window is the go-to pattern for "contiguous subarray/substring" problems. It maintains a window [left, right] and, instead of recomputing from scratch, updates an aggregate as the window slides — collapsing O(n²) or O(n·k) brute force into a clean O(n) pass.

The core idea

There are two kinds:

• Fixed-size window (size k): slide right one step, add the entering element, subtract the leaving element. Answers "max/min/average of every k-length subarray".
• Variable-size window: expand right to include elements; when a constraint breaks (sum too big, duplicate char, too many distinct), shrink from the left until valid again. Track the best window seen.

Efficiency: right advances n times and left advances at most n times total, so it is O(n) even though it looks nested.

Problem type	Window	Time	Space
Max sum of k-length subarray	fixed	O(n)	O(1)
Longest substring w/o repeat	variable	O(n)	O(k) alphabet
Min window covering target	variable	O(n)	O(k)
Count anagrams / permutations	fixed	O(n)	O(1)

Exam Tricks & Tips

• 🎯 Keywords "contiguous", "subarray", "substring", "consecutive" → think sliding window first.
• 🎯 Fixed window: precompute the first k, then slide with add-one/remove-one in O(1).
• 🎯 Variable template: expand while valid, shrink while invalid, update answer after each step.
• 🎯 Use a hash map / count array to track window contents (chars, frequencies).
• 🎯 "Exactly K distinct" = atMost(K) − atMost(K−1).
• ❌ Common mistake: sliding window on "subarray sum ≥ target" with negatives — shrinking is no longer monotonic; use prefix sum + deque instead.

Expected pattern

Longest/shortest/count of subarrays meeting a sum, distinctness, or frequency constraint. Interviewers want the O(n) window plus a clear invariant for when you shrink versus expand.

Quick recap

Slide a window and update an aggregate incrementally. Fixed size → add/remove one per step; variable size → expand-then-shrink on a constraint. O(n) time, O(1)–O(k) space. Beware negatives breaking the monotonic shrink.

Cover the answer, recall, then check. 11 cards on sliding window.

Q1. What class of problems does sliding window solve?
A1. Contiguous subarray / substring problems with a sum, distinctness, or frequency constraint.

Q2. Fixed-size window: how do you update the aggregate per slide?
A2. Add the entering element and subtract the leaving element — O(1) per step, O(n) total.

Q3. Variable-window template in one line?
A3. Expand right to grow the window; while the constraint is violated, shrink from left; update the answer each step.

Q4. Longest substring without repeating characters — complexity?
A4. O(n) time, O(min(n, alphabet)) space using a last-seen map or count array.

Q5. Why is sliding window O(n) despite the inner while-loop?
A5. left only moves forward and never past right, so total left-moves ≤ n; with n right-moves it's O(n).

Q6. "Exactly K distinct" from "at most K"?
A6. exactly(K) = atMost(K) − atMost(K−1).

Q7. When does sliding window break for "subarray sum ≥ target"?
A7. When negatives are present — shrinking no longer strictly decreases the sum, so the monotonic invariant fails.

Q8. Minimum window substring — what tracks validity?
A8. A need-count map plus a "formed" counter; the window is valid when formed == required distinct chars.

Q9. Find all anagrams of p in s — window type?
A9. Fixed window of size |p| with a frequency-match check; O(n).

Q10. Space for a lowercase-only frequency window?
A10. O(1) — a fixed 26-entry array, independent of input length.

Q11. Typical off-by-one in fixed windows?
A11. Forgetting to remove the element at index (right − k) when the window first exceeds size k.

Whenever a question asks about the "best contiguous subarray or substring" — longest, shortest, maximum sum, at most K distinct — the sliding window turns a recompute-everything O(n²) or O(n·k) approach into one O(n) pass.

Core idea: maintain a contiguous window [left, right] and a running summary (sum, count, frequency map). As right expands you add one element; when the window breaks a constraint you shrink from left, removing elements. Nothing is recomputed from scratch.

How it works

Beginner — fixed-size window

"Maximum sum of any subarray of length k": compute the first window's sum, then slide by adding the incoming element and subtracting the outgoing one.

sum = sum(a[0..k-1]); best = sum
for right in k..n-1:
    sum += a[right] - a[right-k]
    best = max(best, sum)

Each step is O(1), so the whole scan is O(n), versus O(n·k) if you re-add k elements each time.

Intermediate — variable-size window

Here the window grows and shrinks to satisfy a constraint. Pattern for "longest substring with at most K distinct characters":

left = 0; freq = {}
for right in 0..n-1:
    freq[a[right]] += 1
    while len(freq) > K:          # constraint broken → shrink
        freq[a[left]] -= 1
        if freq[a[left]] == 0: del freq[a[left]]
        left += 1
    best = max(best, right - left + 1)

Advanced — why it is still O(n)

The inner while looks nested, but left only ever moves forward and never past right. Across the entire run, left advances at most n times total. So the amortised work is O(n) time; space is O(K) or O(alphabet) for the map.

Worked example

Longest substring without repeating characters in "abcabcbb". Expand right, tracking last-seen positions. At the second a (index 3), the window abc would repeat a, so move left past the old a. Windows: abc (len 3) is the max. Answer 3. Each character enters and leaves the window once → O(n).

When to use it

Cue phrases: "contiguous", "subarray/substring", "longest/shortest/maximum", "at most / exactly K". Fixed window when the length is given; variable window when you optimise length under a constraint. "Exactly K" is often computed as atMost(K) − atMost(K−1).

Tricks & gotchas

• Update the running summary incrementally — recomputing sum/frequency inside the loop reintroduces O(n²).
• Shrink with while, not if: several elements may need removing after one expansion.
• Sliding window needs contiguity; for subsequences (non-contiguous) it does not apply.
• Mnemonic: "Grow right, shrink left, keep a running tally."

Worked Example

Problem: Find the maximum sum of any contiguous subarray of size k = 3 in [2, 1, 5, 1, 3, 2].

Solution: Instead of recomputing each window from scratch, slide a fixed window: subtract the element leaving the window and add the one entering.

First window [2, 1, 5] → sum = 8.

Slide right one step at a time:

window	computation	sum
[2,1,5]	initial	8
[1,5,1]	8 − 2 + 1	7
[5,1,3]	7 − 1 + 3	9
[1,3,2]	9 − 5 + 2	6

The maximum window sum is 9 (the subarray [5, 1, 3]).

Sliding makes this O(n) rather than O(n·k) for recomputing every window.

Answer: Maximum sum = 9.