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).
Core idea: keep a sliding window that carries a tiny violation budget — it may contain at most one zero. Expand the right edge greedily; the instant a second zero sneaks in, slide the left edge forward until you've evicted the older zero and you're back under budget. The longest window you ever held, minus one (for the element you're forced to delete), is the answer.
Problem, rephrased
You're handed a binary array nums (just 0s and 1s). You must delete exactly one element — no skipping, even if every element is already a 1. After that single deletion, look at the array and find the longest run of consecutive 1s. Return its length, or 0 if no such run survives.
Here's the mental trick that turns "delete an element" into a sliding window: deleting one 0 from inside a window of mostly-1s stitches the two surrounding runs of 1s together. So instead of literally deleting, we hunt for the longest window that contains at most one zero — that one zero is the element we'll delete, and everything else in the window is the 1s that fuse around it.
nums |
Best window (≤ one 0) | Delete | Resulting run of 1s | Answer |
|---|---|---|---|---|
[1,1,0,1] |
[1,1,0,1] (one 0) |
the 0 |
[1,1,1] |
3 |
[0,1,1,1,0,1,1,0,1] |
[1,1,1,0,1,1] |
middle 0 |
[1,1,1,1,1] |
5 |
[1,1,1] |
[1,1,1] (no 0) |
a 1 (forced) |
[1,1] |
2 |
[0,0,0] |
[0] (one 0) |
the 0 |
[] |
0 |
Notice row 3: there's no zero to delete, but the problem still forces you to remove an element — so the longest run shrinks by one 1. And row 4: the window can hold one zero, but deleting it leaves nothing, so the answer is 0. Both fall out of the same formula: answer = (largest window size) − 1.
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