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).
Minimum Size Subarray Sum
Core idea: You want the shortest contiguous run of numbers whose sum reaches a target. Walk a window across the array with two pointers. Expand the right edge, adding each new number to a running
window_sum. The instant the window is "good enough" (window_sum >= target), don't stop — shrink from the left as far as you can while it stays valid, recording the length at each step. Every time you drop the left number the sum can only decrease (all numbers are positive), so you peel off the left edge until removing one more would break the threshold — that boundary is the shortest valid window ending at the current right edge. Slide right, repeat. Each index is added once and removed once, so the whole sweep is O(n). The trick is that minimizing length means greedily shrinking the left edge — the exact mirror of "grow the right edge to maximize" problems.
The problem, rephrased
You're metering a stream of positive readings — say, water flowing through a pipe sampled second by second. You have a quota: you need to have measured at least target total units. Question: what is the fewest consecutive seconds in which the flow already adds up to the quota? Return that smallest count of consecutive samples; if the whole stream never reaches the quota, return 0.
Formally: given an array nums of positive integers and a positive integer target, find the minimal length of a contiguous subarray whose sum is >= target. Return 0 if no such subarray exists.
This is LeetCode 209 — Minimum Size Subarray Sum.
| Input | Means | Output |
|---|---|---|
target = 7, nums = [2,3,1,2,4,3] |
Smallest contiguous run summing >= 7 |
2 (the run [4,3]) |
target = 4, nums = [1,4,4] |
A single element already hits 4 | 1 (the run [4]) |
target = 11, nums = [1,1,1,1,1,1,1,1] |
Total is only 8, never reaches 11 | 0 |
Note the asymmetry: the constraint is >= target (reach or exceed the quota), and you report the minimal length, not the maximal.
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