Sliding window — every question, written out
A fixed-width window slides across the array, updating its sum with one add and one subtract. The move that turns O(n·k) into O(n). No re-scanning, ever.
Read the sliding window explanation and watch it run
Why is the sliding window O(n) when the obvious loop over windows is O(n·k)?
Complexity derivation
A slide changes exactly two elements, so the summary updates in O(1) whatever k is
Window `a[i..i+k−1]` and its successor share k − 1 elements, so only the entering and the leaving value differ. Adding one and subtracting the other maintains the sum in two operations regardless of k, turning n windows × k work into n windows × O(1). In the trace a slide touches exactly two cells, and that pair is the entire algorithm.
See it run — A slide, and the only two cells involved: a[5] arriving and a[0] departing.
By what factor does the sliding window beat recomputing each window from scratch?
Complexity derivation
By about k — the wider the window, the more the overlap saves
Brute force pays (n − k + 1) windows × k additions while the window pays two operations per slide, so the ratio is k itself. For a day of per-second readings under a one-hour window that is a factor of 3,600 — an instant answer against 300 million operations. The gain is comic at k = 3 and decisive at any realistic width.
Window maxima via a monotonic deque: why is that O(n) when one step can pop many entries?
Complexity derivation
Each index is pushed once and popped at most once, so total pops are bounded by n
The bound is amortised rather than per-step: an index enters the deque exactly once and leaves at most once, so the run performs at most n pushes and n pops. A single slide may pop several entries, but only by spending pushes that were already paid for. Being able to say "per-step cost is unbounded, total cost is linear" is what separates a memorised pattern from an understood one.
In the variable-size form one arrival can trigger many departures. Why is the total still O(n)?
Complexity derivation
Both edges only ever move rightward, so their combined travel is at most 2n
Amortisation: `right` adds each element exactly once and `left` removes each element at most once, so total pointer movement is bounded by 2n however the shrinking clusters. Per-step cost genuinely is unbounded — one arrival can evict most of the window — but no element is ever evicted twice. Saying "amortised" and then giving that counting argument is what the follow-up is fishing for.
What has to remain true after every slide for the technique to be correct at all?
Invariant identification
The maintained summary is exactly the true summary of the window it claims to describe
The invariant is exactness: after one addition and one subtraction, the maintained number must still equal the true sum of `a[L..R]`. It survives because the true sum changes by precisely (entering − leaving), which is exactly what the code applies. When the summary generalises to a frequency table or a distinct count, the obligation is identical — and if you cannot state it for your summary, the pattern does not apply.
See it run — The annotation names window and value together: a[1..5] sums to 48 — the claim, checkable on the spot.
On the sawtooth preset three different windows all sum to 56. Which is reported, and what enforces it?
Invariant identification
The earliest — the strict `>` comparison refuses to displace an equal incumbent
The update is guarded by `if (sum > best)`, so an equal sum leaves both `best` and `bestStart` untouched and the first window to reach 56 keeps the title. Step 92 of the trace shows `a[11..15]` summing to 56 with no new-best line following it, and the closing wash marks `a[3..7]`. Change `>` to `>=` and the same run answers with the last window instead.
See it run — a[11..15] sums to 56, ties the record — and nothing announces a new best.
When `right` enters a window of width k, which index leaves — and what happens if you pick wrong?
Code diagnosis
`right − k` leaves; using `right − k + 1` removes a value still inside the window
Before the slide the window is `a[right−k .. right−1]` and afterwards it is `a[right−k+1 .. right]`, so the departing element is `a[right − k]`. Off by one here subtracts a value that is still inside and keeps one that has gone, and because the sum is never recomputed the error persists for the rest of the run. Nothing crashes and no bound changes — the answer is simply wrong, which is why the invariant is worth stating before writing the line.
A candidate initialises `best = 0` before the loop rather than seeding it with the first window. When does that bite?
Code diagnosis
Whenever every window sums negative: it reports 0, a window that does not exist
A sentinel must be impossible, and 0 is a perfectly possible window sum — worse, it beats every window on all-negative data, so `bestStart` never moves off its initial value. Prism sums the first window honestly and seeds `best` from it, which no non-existent window can outrank. Seed from real data, or from a value the domain genuinely excludes.
Why can a window sum be maintained in O(1) per slide while a window maximum cannot?
Trade-off & selection
A sum is invertible — subtraction undoes a departure — while a max forgets the runner-up
Maintaining a summary incrementally requires the departure to be undoable, and subtraction undoes addition exactly. A maximum is lossy: when the largest value slides out, a single stored number holds no information about the second largest, so it has to be rebuilt. That is why window maxima need a monotonic deque of surviving candidates instead of one accumulator.
"Longest subarray with sum at most S." Why can the fixed-width template not be pointed at it?
Trade-off & selection
The width is the answer, so the window must grow right and shrink left on a condition
Fixed width assumes k is handed to you; here the width is the thing being solved for, so the template becomes "extend right, shrink left while the window violates the condition, then harvest". Correctness rests on monotonicity — removing an element must move a violating window toward validity — which holds for a sum bound over non-negative values. Both edges still travel only rightward, which is why the shape stays linear.
A prefix-sum array also answers any window sum in O(1). What does the sliding window buy over it?
Trade-off & selection
O(1) memory and an online algorithm — it never keeps the data it has passed
Both answer range sums in O(1) after linear setup, so the difference is memory and access pattern. The window holds two numbers and never looks back, which makes it usable on a stream whose data is gone once it has passed; the prefix array holds n numbers and in exchange answers arbitrary ranges in any order. Pick the window for a moving front under a memory limit, and prefix sums when the queries jump about.
The variable-size "longest subarray with sum at most S" template quietly breaks on negative values. Why?
Edge case reasoning
Shrinking can raise the sum, so a violating window is no longer pushed toward validity
The shrink step is only justified when removing an element makes a violating window less violating, which holds for non-negative sums and fails the moment a negative can be removed. With negatives the problem wants prefix sums plus a sorted structure or a monotonic deque, depending on the exact predicate. Noticing that the template carries a precondition — rather than reciting the template — is the point.
Prism derives k as min(5, n). What does a run look like when n equals k exactly?
Edge case reasoning
One window is summed honestly and no slide happens — the whole array is the answer
The warm-up sums `a[0..k−1]` and seeds `best` from it, and the slide loop runs from `k` to `n − 1`, which is empty when n equals k. At size 4 the trace is twenty steps long: four marks, one honest sum, then the closing wash over the whole array. The degenerate case comes out right with no special case, which is the sign the loop was written the correct way round.
See it run — "Window sum 10; best so far 10" — and the very next step is already the answer wash.
A problem asks for the longest SUBSEQUENCE with some property. Why is that a different tool entirely?
Comparison
A subsequence is not contiguous, so no pair of window edges can describe the candidates
A window is a contiguous run described by two edges, so it can only enumerate subarrays, while a subsequence picks an arbitrary ordered subset that two edges cannot represent. The vocabulary is worth memorising: "contiguous subarray" invites the pattern and "subsequence" forbids it, usually pointing at dynamic programming instead. Longest increasing subsequence and longest common subsequence are the standing reminders.
Now the predicate is not monotone at all — "window sum divisible by 7". What replaces the window?
Comparison
Prefix sums with a hash map on residues; a shrink rule has nothing to steer by
A variable-size window needs a predicate where shrinking moves you toward validity, and divisibility supplies no such direction. Prefix sums modulo 7 do: two prefixes sharing a residue bound a subarray divisible by 7, and a map from residue to earliest index finds them in one linear pass. Both tools are O(n) — knowing which one a predicate deserves is the actual skill being tested.
One slide happens. Exactly how many cells change their membership of the window, and which?
Trace prediction
Two: the arriving element joins on the right, the departing one drops off the left
The trace makes it literal: one step unmarks the departing cell, the next marks the arriving one, and no other cell is touched. That two-cell delta is the entire justification for maintaining the sum with one addition and one subtraction. Everything else about the pattern follows from it.
See it run — a[0] unmarked, then a[5] marked — the complete cost of one slide.
The sawtooth run ends. Which window does it mark as the answer, and why not one of the later ties?
Trace prediction
`a[3..7]`, the first window to reach 56 — later ties never displace the incumbent
The closing wash marks indices 3 through 7, the first window to hit 56, and the record was set back at step 35. Two later windows tie it and neither takes over, because the update is guarded by a strict `>`. Had the problem asked for the last such window, that single character is all that would need to change.
See it run — The answer wash starts at index 3 — the earliest of the three windows summing 56.
Explain the sliding window to someone who does not code. Say it out loud before revealing.
Explain it plainly
Imagine a cardboard strip with a slot cut in it, five spaces wide, laid over a row of numbers, and you want the five neighbouring numbers with the biggest total. Add up the first five honestly — that is the only honest addition you will ever do. Now shove the strip one place to the right. Four of the five numbers under the slot are the same four that were there a moment ago; one new number slid into view on the right and one dropped out of sight on the left. So you do not re-add anything: you add the newcomer, subtract the one that left, and you have the new total in two moves instead of five. Keep shoving and keep the best total you have seen. A thousand-wide slot would still cost two moves per shove, which is where this stops being a trick and starts being the difference between instant and hopeless. Where the picture breaks: it only works because the running total can be *undone*. Track the biggest number under the slot instead of the total and the moment that biggest number slides out of view you are stuck — knowing what the maximum was tells you nothing about what the new one is, so you have to keep a little queue of runners-up as well.
The listener should end up able to do the arithmetic themselves and to say why re-adding the middle would be silly. A strong answer names the overlap, the two-operation update, and then admits the limit — that some summaries cannot be undone when a value leaves.