Fixed and variable windows
Every window problem is one of two shapes. The state you keep and the property you test are what change from one problem to the next.
Two shapes
A window is a contiguous stretch [lo, hi] of an array or string that moves from left to
right. In a fixed window its length never changes: both ends move together, one step at a time. In a
variable window the right end moves one step at a time and the left end follows when it has to,
sometimes several steps at once, never backwards.
-
Step 1 / 2
Fixed, length 3: the next step adds a[5] and drops a[2]. Every window of length 3 is visited once.
-
Step 2 / 2
Variable: the longest run with sum at most 8 ending at index 7 starts at 4. When 5 arrives the sum is 13, so lo moves right until the sum is back within 8.
The state, and why it must update in O(1)
A window is only fast if what you know about it can be updated when one element enters or leaves, without looking at the rest. That summary is the window's state. Choosing it is most of the design.
| The question asks about | State to keep | Update on enter / leave |
|---|---|---|
| a sum or average | the running total | add / subtract |
| how many of something | a counter | +1 / −1 when it matches |
| distinct values, anagrams, coverage | a count per value, and the number of nonzero counts | adjust one count; the number changes by at most 1 |
| the last place a value was seen | a map from value to index | overwrite; jump lo past the old index |
| the maximum or minimum | a monotone deque of indices | pop dominated entries / pop the front when it leaves |
| a product of positive numbers | the running product | multiply / divide |
If the only way you can see to update the state is to recompute it over the whole window, the window gives you nothing over the double loop. Look for a different state before giving up on the window.
The two templates
Fixed window of length k
fixed(a, k)
- Build the state from a[0 .. k − 1] and record it.
- For hi from k to n − 1: add a[hi], remove a[hi − k], record.
Variable window, longest valid
longest(a)
- lo = 0. For each hi: add a[hi] to the state.
- While the window is invalid: remove a[lo] and move lo right.
- The window is now the longest valid one ending at hi: record hi − lo + 1.
The variable template has two mirror images, for the shortest valid window and for counting, which have their own modules. In all of them each index enters the window once and leaves at most once, so the work is at most 2n state updates however often the window changes size.
With O(1) updates the scan is linear. With a sorted container or heap as the state it is O(n log n), which is still often the intended answer.
Three questions before you write the loop
- Is the answer a contiguous run? Subsequences, subsets and pairs are not windows.
- Which way does validity go? If every run inside a valid run is valid ("at most k distinct", "sum at most B" with positive numbers), shrink while invalid and look for the longest. If every run containing a valid run is valid ("covers every letter", "sum at least K" with positive numbers), shrink while valid and look for the shortest. If neither holds, a single window will not do; the last module shows what to use.
- What is the state, and does it update in O(1)? The table above covers almost every question asked in interviews.
Saying these three answers aloud before coding is also what interviewers listen for. It shows that you are using the window because it is correct, not because the question mentioned a substring.
How this chapter is organised
One module per shape: fixed windows; the longest valid window; the shortest valid window; counting windows; windows whose state is a maximum or minimum; and, last, how to recognise the problems that look like windows and are not. Each module opens with a lesson, then its problems from easy to hard.