Cost
| Operation | Time | Space | Why |
|---|---|---|---|
| Variable window (longest / shortest run) | O(n) | O(k) | Each index enters the window once and leaves once, so the two edges make at most 2n moves. k is the number of distinct items tracked. |
| Fixed window of size k | O(n) | O(1) | Add the entering element, subtract the leaving one. Recomputing the whole window each step is the common mistake and costs O(n·k). |
| Brute force over all subarrays | O(n²) | O(1) | What the window replaces. Validating each subarray from scratch makes it O(n³); the window keeps the running state instead. |
| Exactly k distinct (via at-most) | O(n) | O(k) | "Exactly k" is not monotone, so it is solved as atMost(k) − atMost(k−1): two linear windows rather than one clever one. |
Reach for it when
- "Longest" or "shortest" contiguous run satisfying some property.
- Fixed-size statistics — max sum or average of every k consecutive elements.
- Counting subarrays whose contents satisfy a bound, often via the at-most trick.
- Anagram and permutation matching inside a string, where the window is a character count.
- Rate limiting, moving averages, and stream de-duplication — the same structure outside interviews.
Two shapes
Fixed size. The window is k wide and stays k wide. Every step adds the element entering on the right and removes the one leaving on the left, so the running total is maintained rather than recomputed.
def max_sum_k(nums, k):
total = sum(nums[:k])
best = total
for right in range(k, len(nums)):
total += nums[right] - nums[right - k] # in, out
best = max(best, total)
return bestVariable size. The window grows on the right whenever it can and shrinks on the left whenever it must. This is the shape in the visualisation above, and the template is worth memorising:
def shortest_at_least(nums, target): # positive numbers only
left = total = 0
best = float("inf")
for right, value in enumerate(nums):
total += value # grow
while total >= target: # shrink while valid
best = min(best, right - left + 1)
total -= nums[left]
left += 1
return 0 if best == float("inf") else bestGrow unconditionally, shrink conditionally, record the answer where the window is valid. Almost every variable-window problem is this loop with a different notion of "valid".
The monotonicity requirement
A window only works if validity behaves predictably as the window changes. Concretely: shrinking must never turn a valid window invalid, and the answer must be recoverable by sweeping the right edge once.
With positive numbers, "sum ≥ target" qualifies — removing an element can only lower the sum. Allow negatives and it collapses: a window that is too small might become valid by extending right, so the left edge has no rule to follow. That problem becomes prefix sums plus a hash map, which handles negatives because it compares totals rather than sliding a span.
The one-line check before writing any window: if I remove an element from the left, can the window become more valid? If the answer is no, stop and pick another tool.
Why the nested loop is still O(n)
The shrink loop sits inside the grow loop, which looks quadratic and is not. The left edge never moves backwards, so across the entire run it advances at most n times total. The right edge does the same. Two counters, each bounded by n, gives at most 2n moves regardless of how the work is distributed between the loops.
This is the amortized argument, and it is the answer to "what's the complexity?" — not the number of loops on screen.
Relation to two pointers
A sliding window is a two-pointer method; the difference is what the pointers mean. In Two Pointers, the region between the pointers is what has not yet been ruled out, and the pointers converge. Here the region between them is the candidate answer, and both move the same direction. The invariant is inverted: there, everything outside the pointers is eliminated; here, everything inside them is valid.
What to say in the interview
Name the window, name the invariant, then give the cost with its amortized justification: "the right edge visits each index once and the left edge only moves forward, so it is O(n) time and O(k) space." Then say why a window is legal here at all — that the validity condition is monotone. That last sentence is what separates a memorised template from an understood one.
Where candidates slip
- Using a window where validity is not monotone. "Sum ≥ k" with negative numbers breaks it — shrinking can make an invalid window valid again, so the edges have nothing to steer by. That case wants prefix sums, not a window.
- Recomputing the window's contents on every step. That quietly restores the O(n·k) you were trying to remove; the window must be updated incrementally as elements enter and leave.
- Shrinking with
ifwhen the fix needs a loop. One removal may not restore validity —whileis the default, andifonly when a single step provably suffices. - Moving the left edge backwards. The linear bound depends on it never rewinding; if your logic wants to, the window is the wrong tool.
- Off-by-one in the size. A window of
[left, right]inclusive hasright - left + 1elements, and best should be recorded when the window is valid, not after a shrink step that has not finished.