Lesson 13 of 16 · 20:31
Sliding window
A sliding window represents a contiguous region and maintains a summary of that region as its boundaries move. Instead of recomputing every substring or subarray from scratch, add the entering item and remove the leaving item.
The pattern works when validity can be repaired monotonically by moving the left boundary. The invariant must connect the boundaries, the stored summary, and the moment at which an answer is recorded.
What you should be able to do after this lesson
- Define exactly what the window contains
- Keep entry and exit updates symmetric
- Prove that moving left repairs validity
The mental model
Right expands the candidate window; left repairs it. A small summary—sum, counts, distinct keys, max structure—represents the current range.
Recognize it when: Use a window for longest, shortest, maximum, minimum, count, or validity questions over contiguous subarrays or substrings when state can be updated locally.
The invariant to say aloud: After the repair loop, the active window satisfies the validity condition and its maintained summary exactly matches the elements inside [left, right].
Learn the ideas one at a time
Concept 1 of 5
Variable-size window
Watch from 0:56 ↗Expand right to include a new item. While the window violates the rule, remove arr[left] from state and advance left. Record the answer at the contractually correct moment.
Expand right to consider a new item. If the window becomes invalid, repeatedly remove the leftmost item until the invariant is restored. Depending on the question, record the best window after repair, before repair, or at the exact moment a condition becomes true.
Walk through an example
For the longest substring without repeats, add the right character to a frequency map. While its count exceeds one, decrement characters from the left and advance left. Once valid, update the maximum length.
In an interview
Say why removing from the left moves the window toward validity. If it can make the condition worse unpredictably, this template is not justified.
Concept 2 of 5
Fixed-size window
Watch from 12:43 ↗Build the first k-item summary, then add the entering item and remove the leaving item for each shift. Every later window costs O(1) update work.
When every candidate has length k, build the summary for the first k items. Each shift adds one entering value and removes one leaving value, so the next candidate is updated in constant work rather than rescanned.
Walk through an example
For k=3 and values [2,1,5,1], first sum is 8. Shift right: add 1 and subtract 2 to get 7. The overlapping values 1 and 5 were never summed again.
In an interview
Handle k=0, k greater than n, and the exact point at which the first complete window exists.
Concept 3 of 5
Window state
Watch from 0:56 ↗The summary may be a scalar sum, a frequency map, a distinct count, or a monotonic deque. Update it symmetrically on entry and exit.
State may be a sum, frequency table, distinct count, maximum structure, or another incremental summary. It must describe exactly the elements between left and right. Any derived counter must be updated when frequencies cross the threshold it represents, not on every raw increment.
Walk through an example
If distinct counts keys with positive frequency, adding a character changes distinct only when its old count was zero; removing changes distinct only when its new count becomes zero.
In an interview
Write the meaning of each state variable in plain language. Most window bugs are stale state rather than boundary arithmetic.
Concept 4 of 5
Why it is O(n)
Watch from 0:56 ↗Right advances n times and left advances at most n times. The repair loop is amortized O(n), even though it is nested inside the expansion loop.
Right enters each position once. Left can only move forward and removes each position at most once. The inner repair loop may run many times in one iteration, but across the entire algorithm it performs at most n removals.
Walk through an example
Even if left jumps ten positions after one new value, those ten positions are gone forever. Future iterations cannot charge removal work to them again.
In an interview
Explain amortization by counting each element's one entry and one exit, giving at most 2n boundary events.
Concept 5 of 5
When it fails
Watch from 0:56 ↗If removing the leftmost item does not move validity monotonically toward repair, a standard window may not apply; prefix sums, DP, or another structure may be needed.
A standard variable window needs a one-direction repair rule. With arbitrary negative numbers, removing the leftmost value can increase or decrease a sum unpredictably, so “sum too large, move left” may discard a future optimum. Prefix sums, ordered maps, or dynamic programming may be needed.
Walk through an example
For a positive-only sum, removing left always decreases the sum. With a negative left value, removing it increases the sum, breaking the monotonic repair argument.
In an interview
Check the data assumptions—especially positivity and monotonicity—before applying a familiar window template.
Before you call this lesson done
- Define inclusive/exclusive boundaries
- Update state on both entry and exit
- Record the answer at the correct moment
- Verify monotonic repair assumptions
