← Sliding Window · guided lesson
Sliding Window
the story
Fixed-size sliding window
Every tool here exists because something was too slow or broke without it. Here is what.
Running totals over the last k values are as old as moving averages in statistics; as an array technique it is programming folklore, and we found no single inventor to credit.
why it matters: without it
Every rolling average or "last k" check would re-scan its whole window: O(n·k) work, which turns into crores of operations on a single day of per-second data.
also in this chapter: Variable-size window (grow and shrink) · Monotonic deque (max / min of every window)
the idea
The idea in 30 seconds
Many questions ask about the best contiguous subarray or substring. Checking every one is O(n²) or worse.
Instead, keep a window [left, right] and a small summary of it (a sum, a count table). When the window moves, update the summary: one element in, one element out.
right only moves forward and left only moves forward, so each element is added once and removed once: O(n).
picture this
Task Manager's CPU graph shows only the last 60 seconds. Every second, one new reading appears on the right and the oldest drops off the left — the whole minute is never redrawn. A sliding window updates its summary the same way: one in, one out.
watch it
Fixed window — one in, one out
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Fixed window — one in, one out
The window keeps its size. Each slide is two operations — add the new number, drop the oldest — not k.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Variable window — grow, then shrink
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Variable window — grow, then shrink
`right` grows the window until the sum is big enough; `left` shrinks it while it stays valid.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 8
Read it once. Say it out loud once. Bas.
Fixed window (size k is given): build the first k, then each slide adds nums[right] and removes nums[right - k].
key idea 2 of 8
Read it once. Say it out loud once. Bas.
Variable window (find the longest / shortest valid slice): grow with right; while the window breaks the rule, shrink with left.
key idea 3 of 8
Read it once. Say it out loud once. Bas.
The window state is whatever lets you answer "is this window valid?" in O(1): a running sum, a zero count, an int[26] letter count, a HashMap.
key idea 4 of 8
Read it once. Say it out loud once. Bas.
Longest valid window → record the answer after the shrink loop. Shortest valid window → record it inside the shrink loop, before each shrink.
key idea 5 of 8
Read it once. Say it out loud once. Bas.
Shrinking is only safe when the rule is monotonic: if a window is invalid, every bigger window containing it is invalid too (for shortest problems, the mirror: if a window is valid, every bigger one is valid). Negative numbers usually break this for sums.
key idea 6 of 8
Read it once. Say it out loud once. Bas.
The nested while does not make it O(n²): left moves at most n times in total over the whole run (amortized O(1) per step).
key idea 7 of 8
Read it once. Say it out loud once. Bas.
Need the max or min of every window? Keep a monotonic deque of indices — the front is always the answer.
key idea 8 of 8
Read it once. Say it out loud once. Bas.
Sliding window is same-direction two pointers where you care about everything between the pointers, not just the two ends.
spot the pattern
When you see this, think this
"Contiguous subarray" or "substring" + longest / shortest / maximum / minimum
Variable sliding window
"Of size k", "every k consecutive", "average of each window"
Fixed sliding window
"At most k" distinct / zeros / replacements
Variable window; shrink while the count exceeds k
"Contains all characters of", "anagram", "permutation of" inside a longer string
Window + count array (fixed size for permutations, variable for covering)
+4 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Using
ifinstead ofwhileto shrink — one new element may need several removals. - Recording the answer in the wrong place: longest → after the shrink loop; shortest → inside it.
quick check
One question. No pressure.
Fixed window, k = 3, nums = [2, 1, 5, 1, 3]. The first window sum is 8. What is the sum after one slide?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Longest Substring Without Repeating Characters
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
There's a while inside a for. Why is the variable window still O(n)?
Question 1: There's a while inside a for. Why is the variable window still O(n)?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.