Sliding window
A window that grows on the right, shrinks on the left, and holds an invariant at all times.
When it applies
Use a window when the answer is a contiguous run and there is a property that breaks as the run grows and can be repaired by dropping elements from the left. Because the left edge never moves backwards, the scan stays linear however often the window resizes.
Signals: "longest substring such that", "subarray with sum at most", "at most k distinct", "minimum window containing".
The template
Write this from memory. Every problem in this section is a specialisation of it, and most bugs come from deviating without a reason.
lo = 0
for hi, x in enumerate(a):
add(x) # extend the window to the right
while violates(): # repair it from the left
remove(a[lo]); lo += 1
best = max(best, hi - lo + 1)int lo = 0, best = 0;
for (int hi = 0; hi < (int)a.size(); ++hi) {
add(a[hi]);
while (violates()) remove(a[lo++]);
best = std::max(best, hi - lo + 1);
}int lo = 0, best = 0;
for (int hi = 0; hi < a.length; hi++) {
add(a[hi]);
while (violates()) remove(a[lo++]);
best = Math.max(best, hi - lo + 1);
}let lo = 0, best = 0;
for (let hi = 0; hi < a.length; hi++) {
add(a[hi]); // extend right
while (violates()) remove(a[lo++]); // repair from the left
best = Math.max(best, hi - lo + 1);
}let (mut lo, mut best) = (0usize, 0usize);
for hi in 0..a.len() {
add(a[hi]);
while violates() { remove(a[lo]); lo += 1; }
best = best.max(hi - lo + 1);
}-- Fold carrying (state, window start, best)
foldl step (empty, 0, 0) (zip [0..] xs)
where step (st, lo, best) (hi, x) =
let st' = add x st
(st'', lo') = shrink st' lo
in (st'', lo', max best (hi - lo' + 1))Problems
Best total over k consecutive days
A window of fixed width slides one place at a time: add the element that enters, subtract the one that leaves.
Open the problem → Easy12 minLongest run of tasks within a time budget
With positive numbers, a run that is over budget only gets worse as it grows, so the left end never moves back.
Open the problem → Easy10 minMost vowels in any k letters
The same fixed window as a running sum, with a count of the letters that matter as its state.
Open the problem → Medium15 minShortest subarray with a sum at least the target
A window that grows on the right until it qualifies, then shrinks on the left while it still does.
Open the problem → Medium20 minCount runs whose product is below k
Counting windows rather than measuring them: once the window ending at hi is the longest valid one, all of its suffixes are valid too.
Open the problem → Medium15 minLongest run of distinct characters
The window that grows on the right and shrinks on the left, and the invariant that makes it correct.
Open the problem → Medium20 minCount substrings holding a, b and c
When validity survives growing, count from the other side: after shrinking to the last valid start, every earlier start works too.
Open the problem → Medium20 minShortest window holding every kind
For the shortest valid window the loop turns inside out: record the answer while the window is valid, and shrink to find the next one.
Open the problem → Medium25 minLongest run whose spread is at most a limit
The validity test needs the window's maximum and minimum. Two monotone deques keep both as the window slides.
Open the problem → Medium20 minEvery place an anagram begins
Compare a window's letter counts with a pattern's in O(1) per step by tracking how many letters still differ.
Open the problem → Medium20 minLongest run with at most k distinct letters
The variable window in its plainest form: grow on the right, and while the window breaks the rule, shrink on the left.
Open the problem → Medium15 minDistinct values in every window
Keep a count per value, not a set: a set cannot tell whether the value leaving still has a copy inside.
Open the problem → Medium15 minLongest run of ones after k flips
Rephrase "flip at most k zeros" as "a window with at most k zeros", and a counter is all the state you need.
Open the problem → Medium15 minThe best stretch to stay calm
Split the answer into a part no choice can change and a part the window controls, then slide over the second.
Open the problem → Medium25 minLongest run of one letter after k changes
A window is fixable when its length minus its most common letter is at most k. The subtle part is that the most common count never has to go down.
Open the problem → Medium15 minLongest run of ones after deleting one element
Deleting one element joins two runs of ones across a zero: a window with at most one zero, whose length is one more than the answer.
Open the problem → Hard25 minMaximum of every window
A deque of candidates, kept in falling order, gives the maximum of every window in one pass.
Open the problem → Hard30 minCount runs with exactly k distinct values
"Exactly k" is not monotone, so no single window counts it. Two windows that count "at most" do, and their difference is the answer.
Open the problem → Hard30 minShortest window containing every letter
Count what the window still needs; extend on the right until nothing is missing, then cut from the left.
Open the problem → Hard35 minShortest run with sum at least K, negatives allowed
Negative numbers break the plain window. Prefix sums turn the question into pairs of indices, and a deque keeps only the starts that can still win.
Open the problem →Or sit a timed interview: a fixed window, limited submissions, and a report at the end.