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).