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).
Fruits into Baskets
Core idea: Grow the window greedily to the right, one element at a time. Only when the window breaks the constraint (more than 2 distinct types) do you shrink from the left — just enough to make it valid again. The longest the window ever gets is your answer. Each element enters once and leaves once → O(n).
Problem, rephrased
You're walking down a single row of fruit trees. Tree i grows fruit of type fruits[i] (think apple, banana, cherry…). You carry two baskets, and each basket can hold only one type of fruit — but unlimited quantity of it.
You pick one starting tree, then walk strictly rightward, grabbing one fruit from every tree you pass. You must stop the moment you'd need a third type (you only have two baskets). You want to start at the spot that lets you collect the most fruit total.
Strip away the story and it's this: find the length of the longest contiguous subarray that contains at most 2 distinct values. ("Contiguous" because you can't skip trees — you walk a straight row.)
Inputs / outputs
fruits |
longest valid run | answer |
|---|---|---|
[1, 2, 1] |
[1, 2, 1] |
3 |
[0, 1, 2, 2] |
[1, 2, 2] |
3 |
[1, 2, 3, 2, 2] |
[2, 3, 2, 2] |
4 |
[3,3,3,1,2,1,1,2,3,3,4] |
[1, 2, 1, 1, 2] |
5 |
You return the length of that best run, not the fruits themselves.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson