The signal#
Reach for a window when a question is about a contiguous stretch of a list or string, and asks for the best or the count of such stretches. "Subarray" and "substring" mean contiguous. "Subsequence" does not, and a window is the wrong tool for those.
Fixed size first#
The window is k wide and slides one step at a time. Sliding means exactly one element joins on the right and exactly one leaves on the left:
for right in 0 .. n-1:
add nums[right]
if right >= k - 1:
record the window
remove nums[right - k + 1]
The only real requirement is that whatever you track can be undone. A running sum can: adding a number and subtracting it cancel out. A maximum cannot, which is why "maximum in every window" needs a deque and is a harder problem than it looks.
| what you track | joining | leaving |
|---|---|---|
| sum | add it | subtract it |
| count of vowels | add one if it is a vowel | subtract one if it was |
| first negative | push its position if negative | pop the front if it has fallen out |
| maximum | not reversible, needs a deque |
Variable size#
Now the window has no fixed width. Instead there is a rule it must obey, and you want the longest (or shortest) window that does.
left = 0
for right in 0 .. n-1:
add nums[right]
while the window breaks the rule:
remove nums[left]
left += 1
record the window
That inner while is the whole difference. Read it as: the right edge takes ground, and the left edge gives back only as much as it must.
Longest or shortest changes where you record#
This trips people up, so it is worth stating flatly.
For a longest window, the rule is "still legal", and you record after the while loop, when the window has just been made legal again.
For a shortest window, the rule is "not yet good enough", and you record inside the loop, as you shrink: each shrink gives a smaller window that still satisfies the condition, and the last one before it breaks is the best from this right edge.
Minimum size subarray sum is the shortest kind. Longest substring without repeating characters is the longest kind. Solving one straight after the other is the fastest way to feel the difference.
Why the nested loop is not n squared#
The code has a loop inside a loop, which looks like n squared and is not. The left edge only ever moves right, and it can only move n times in total across the entire run. So the inner loop's total work over the whole algorithm is at most n steps, not n per outer step.
Being able to say that sentence in an interview is worth more than remembering the template.
Finding the window hiding in the words#
Most window problems arrive in disguise. Translating them is the real skill:
| The question | What it means |
|---|---|
| Two baskets, one fruit type each | Longest stretch with at most 2 distinct values |
| Flip at most k zeros | Longest stretch with at most k zeros |
| Replace k characters to get a repeat | Longest stretch where (length minus the commonest count) is at most k |
| Smallest stretch containing every letter of a word | Shortest stretch whose counts cover a target |
Every one of them becomes the same nine lines once it is translated.
Where a window does not work#
The window needs the rule to be monotone: if a window is illegal, growing it further cannot make it legal again. That holds for counts of distinct values, and for sums when every number is non-negative.
It breaks the moment negatives enter. "Shortest subarray with sum at least k" on a list containing negative numbers is not a window problem, because shrinking from the left can increase the sum. That one needs prefix sums and a deque. If you find yourself fighting a window, check whether this assumption is the thing that failed.
Practice in order#
- The best k days in a row, for the fixed window and the reversible update.
- First negative in every window, for a fixed window holding a queue rather than a number.
- Minimum size subarray sum, the shortest-window form.
- Longest substring without repeating characters, the longest-window form.
- Fruit into baskets and the longest run of ones with k flips, both of which are the same question wearing different clothes.
- Longest repeating character replacement, which is the one that makes you think.