Topic 4 of 20
Sliding Window
Maintain a window over a sequence and update it incrementally instead of recomputing.
The concept
A sliding window is a contiguous range [left, right] that you move across an array or string, updating a small summary (a sum, a count, a frequency map) as elements enter and leave. Because each element enters and leaves the window at most once, problems that look like "check every subarray" (O(n²) or worse) drop to O(n).
There are two flavours. A fixed-size window of length k simply slides one step at a time. A variable window grows by moving right and shrinks by moving left whenever the window becomes invalid, so at every step you know the best valid window ending at right. Most "longest/shortest substring such that…" questions follow this template exactly.
Two advanced tricks round out the topic. To count subarrays with exactly k of something, compute at most k minus at most k−1. To get the maximum of every window in O(n), keep a monotonic deque of candidates. Master the template and a large family of Medium problems becomes routine.
Patterns you will learn
Problems, in order
- 1
Track the best buy so far; the gentlest window-style problem and extremely common.
Running MinimumReported at: AmazonMetaMicrosoft+20 - 2
The textbook fixed window: add the new element, drop the old one.
Fixed-size WindowReported at: Meta - 3
A window of size k kept in a set.
Fixed-size Window + Hash SetReported at: MetaGoogleAmazon+4 - 4
Sorting makes the best window contiguous.
- 5
The canonical variable window; one of the most-asked questions anywhere.
Variable Window (Shrink When Invalid)Reported at: AmazonMicrosoftMeta+16 - 6
The 'window length − max frequency ≤ k' invariant is a classic insight.
Variable Window + Frequency MapReported at: GoogleAmazonUber+1 - 7Permutation in StringMedium
Compare frequency maps incrementally as the window slides.
Fixed-size Window + Frequency MapReported at: MicrosoftAppleAmazon+4 - 8
Same as Permutation in String but collecting every match.
Fixed-size Window + Frequency MapReported at: AmazonMicrosoftMeta+6 - 9
Shrinks while the window is valid, the mirror of the longest-window template.
Variable Window (Shrink While Valid)Reported at: MetaAmazonMicrosoft+4 - 10Max Consecutive Ones IIIMedium
'At most k zeros' is the standard budget-constrained window.
Variable WindowReported at: MetaGoogleMicrosoft+4 - 11Fruit Into BasketsMedium
Longest window with at most two distinct values, in disguise.
Variable Window + Frequency MapReported at: Amazon - 12
Counting subarrays ending at each right index; a key counting trick.
Variable Window (Counting)Reported at: AmazonMetaGoldman Sachs - 13
Introduces the 'exactly = at most − at most' trick.
- 14
The same trick applied to odd-number counts.
- 15
Maximise the ends by minimising the middle window, a neat reframing.
Fixed-size Window (Complement)Reported at: GoogleAmazonAdobe - 16
Sorting plus a window-sum budget check.
- 17
The flagship Hard window problem; a Meta and Google classic.
Variable Window + Frequency MapReported at: MetaAmazonMicrosoft+6 - 18
Introduces the monotonic deque for O(n) window maxima.
Monotonic DequeReported at: AmazonGoogleMicrosoft+10 - 19
The hardest application of the at-most trick.
- 20
Slides in word-sized steps with a frequency map of words.
Window over Word BucketsReported at: AmazonGoogleApple+2