Fixed & Variable Windows
What is this?
Picture a frame that slides across a row of numbers, lighting up a stretch of them like a moving spotlight. A window comes in two shapes: a fixed one that stays the same width and just rolls forward, and a variable one that stretches wider or pulls in tighter as the data demands. Either way, you only update what changed at the edges instead of re-scanning everything.
💡 Fun fact: Fixed-size sliding windows are exactly how moving-average filters work in audio and signal processing — smoothing out a noisy sound or stock chart by averaging the last few samples as the window glides along.
🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: A sliding window turns an O(n²) "check every subarray" into one O(n) pass by reusing the previous window's work. Two shapes cover most problems: a fixed-width window that rolls one step at a time (update +entering / −leaving), and a variable window that expands to grow a quantity, then shrinks to restore a constraint.
The two shapes
Fixed windows answer "best/quantity over every length-k span." Variable windows answer "longest/shortest span satisfying a constraint" — the right edge always advances; the left edge only moves to keep (or restore) validity, so each index enters and leaves at most once → O(n).
The problems
- Maximum Average Subarray I — the fixed-window intro: roll the sum in O(1) per step.
- Fruits into Baskets — longest window with at most 2 distinct (the "at most k distinct" template).
- Minimum Size Subarray Sum — shortest window reaching a target; shrink while still valid.
- Longest Subarray of 1's After Deleting One — a window carrying a violation budget (at most one zero).
Key takeaways
- Reuse, don't recompute — the window's answer is one cheap edit from the next.
- Fixed = roll (+in/−out); variable = expand then shrink to stay valid.
- Each index enters/leaves once ⇒ O(n) even with the inner shrink loop.
- "Longest" shrinks on invalidity; "shortest" shrinks on validity — mirror images.
- Why interviewers love it: it's the cleanest "turn O(n²) into O(n)" move on sequences.
Start here: Maximum Average Subarray I (fixed), then Fruits into Baskets (variable).