Sliding Window
There is a specific kind of wasted work that Sliding Window exists to kill. You are scanning every block of k consecutive elements, and for each block you sum all k values from scratch. The first window adds elements 0 through k-1. The second adds 1 through k. You just re-added almost the same numbers you had a moment ago. Do that across a long array and you have quietly turned an O(n) problem into O(n*k) for no reason at all. The fix is almost too simple to feel like a technique: when the window slides one step, add the element coming in and subtract the one going out.
The fixed window: reuse, do not recompute
Start with the toy that makes the idea obvious. You want the busiest three-hour stretch from a list of hourly visitor counts. Compute the first window's sum once, then slide it along, patching the total as you go:
def max_window_sum(arr, k):
if len(arr) < k:
return None
window = sum(arr[:k])
best = window
for i in range(k, len(arr)):
window += arr[i] - arr[i - k] # add the entering element, drop the leaving one
best = max(best, window)
return best
A trace on [10, 20, 30, 40, 50] with k = 3:
| window | contents | sum | how |
|---|---|---|---|
| 0..2 | 10, 20, 30 | 60 | initial sum |
| 1..3 | 20, 30, 40 | 90 | +40, then -10 |
| 2..4 | 30, 40, 50 | 120 | +50, then -20 |
Three additions instead of nine, and the gap only widens as the array grows. O(n) time, O(1) space, each element entering and leaving exactly once.
Those exact five hours are runnable in the DSA Lab: scrub the slide one addition and one subtraction at a time, and once you reach the variable version below, switch the mode to "Window (min len)" to watch a window grow and shrink instead.
Interactive playground for algorithm patterns: two pointers and sliding windows on a scrubbable timeline, binary search and search-on-the-answer, sorting comparison (6 algorithms), trees (BST, AVL, Heap, Trie), graph algorithms (Cycle Detection, MST, SCC, Max Flow) and hash collision strategies. Every configuration is deep-linkable.
The variable window in the wild: the shortest covering slice
The fixed case is the warm-up. The pattern earns its reputation when the window's size is not handed to you and you grow and shrink it to keep some condition true. A real place this shows up is distributed tracing. You have a time-ordered log of spans, each tagged with the service that emitted it, and you want the shortest contiguous slice of that log in which every service in a required set appears at least once, the tightest window that still reproduces a full end-to-end path.
That is the minimum-window problem, and it is the whole variable-window template in one shot: push the right edge out until the window covers everything required, then pull the left edge in as far as it will go while it still covers everything, recording the smallest span you ever reach.
from collections import Counter
def shortest_covering(spans, required):
need = Counter(required)
missing = len(required) # how many required hits we still lack
left = 0
best = None
for right, svc in enumerate(spans):
if need[svc] > 0:
missing -= 1 # this span covers something we needed
need[svc] -= 1
while missing == 0: # window is valid, try to tighten it
if best is None or right - left + 1 < best[1] - best[0]:
best = (left, right + 1)
need[spans[left]] += 1
if need[spans[left]] > 0:
missing += 1 # dropping this span breaks coverage
left += 1
return None if best is None else spans[best[0]:best[1]]
The expensive-looking pair of loops is still linear: right sweeps forward once and left only ever moves forward, so each span is added once and removed once. That is the same promise the fixed window made, extended to a window that breathes. And it is genuinely the same class of problem as the three-hour peak, just with "valid" defined by coverage instead of a fixed length.
The trigger
A contiguous run in an array or string, plus a word like longest, shortest, maximum, minimum, or "at most k of something." Contiguous is the keyword. If the problem lets you reorder or cherry-pick elements, it is probably not a window. If the answer has to be one solid, unbroken stretch, it usually is.
Where it shows up
- Fixed size: max or min sum of a
k-length subarray, a rolling average, anything phrased as "for every window of k." - Variable size: longest substring without repeated characters (expand, and shrink past the duplicate), the smallest subarray whose sum reaches a target, the shortest window covering a required set.
- Window plus a helper: "at most k distinct values" wants a hashmap of counts inside the window; "maximum of every window" wants a monotonic deque so you never rescan.
Where it bites
Two mistakes recur. First, forgetting the window must stay contiguous: the moment you are tempted to skip a bad element instead of shrinking from the left, you have wandered out of sliding-window territory. Second, botching the shrink, either using an if where the invariant needs a while to fully recover, or recording your answer at the wrong moment, before the window is valid again rather than after. When a variable window is off by a hair, the culprit is almost always whether you update the result inside or after the shrink.
When a window will not save you
The window is the wrong lens the instant the answer stops being contiguous. If you are free to reorder or cherry-pick elements, you are looking at sorting, a heap, or a hashmap, not a window. It also quietly fails when the window's quantity cannot be updated incrementally: a sum or a count adjusts in O(1) as the window moves, but a median does not, so a plain window will not rescue you there without a heap or a balanced multiset riding along. Recognizing that boundary is what keeps you from bending a window around a problem that was never shaped like one.
Where it connects
Underneath, a window is just Two Pointers both marching left to right with a rule about the space between them. When the question is a sum over an arbitrary range that is not sliding, Prefix Sum answers it in constant time per query instead. And the instant the window needs a running maximum or a tally of distinct items, it borrows from a Monotonic Queue or from Hashmaps and Frequency Counting to keep every step cheap.
References
- Introduction to Algorithms (CLRS), 4th ed., Cormen, Leiserson, Rivest, Stein, 2022
- The Algorithm Design Manual, 3rd ed., Steven Skiena, 2020