Sliding Window
Fixed and variable windows, the amortised argument that makes a nested-looking loop O(n), and the condition that decides whether a window works at all.
Sliding window turns “check every subarray” into one pass. The pattern is short; the parts that get probed are the amortised argument and the condition for shrinking.
The signal
"contiguous subarray" → window
"substring" → window
"longest / shortest ... such that" → variable window
"of size k" → fixed window
"maximum sum of k elements" → fixed windowIf the elements do not have to be contiguous, it is not a window problem — that is usually sorting or a heap.
Fixed window
import time, random
from collections import Counter, defaultdict
def max_sum_k_brute(nums, k):
return max(sum(nums[i:i+k]) for i in range(len(nums) - k + 1))
def max_sum_k_window(nums, k):
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k] # add one, drop one — O(1) per step
best = max(best, window)
return best
nums = [random.randint(1, 100) for _ in range(50_000)]
t0 = time.perf_counter(); a = max_sum_k_brute(nums, 500); t1 = time.perf_counter()
b = max_sum_k_window(nums, 500); t2 = time.perf_counter()
print(f"brute O(n·k) {t1-t0:7.4f}s → {a}")
print(f"window O(n) {t2-t1:7.4f}s → {b}")brute O(n·k) 1.4102s → 30184
window O(n) 0.0084s → 30184“The brute force recomputes the whole sum for every position, so it is O(n·k). The window reuses the previous sum — add the entering element, subtract the leaving one — which is O(1) per step and O(n) overall. Note the brute force also allocates a slice each iteration, so it is paying twice.”
Variable window: longest without repeats
def longest_unique_brute(s):
best = 0
for i in range(len(s)):
seen = set()
for j in range(i, len(s)):
if s[j] in seen:
break
seen.add(s[j])
best = max(best, j - i + 1)
return best
def longest_unique_window(s):
last_seen = {}
start = best = 0
for i, ch in enumerate(s):
if ch in last_seen and last_seen[ch] >= start:
start = last_seen[ch] + 1 # jump past the previous occurrence
last_seen[ch] = i
best = max(best, i - start + 1)
return best
s = "".join(random.choices("abcdefghij", k=40_000))
t0 = time.perf_counter(); a = longest_unique_brute(s); t1 = time.perf_counter()
b = longest_unique_window(s); t2 = time.perf_counter()
print(f"brute O(n²) {t1-t0:7.4f}s → {a}")
print(f"window O(n) {t2-t1:7.4f}s → {b}")
for case in ["abcabcbb", "bbbbb", "pwwkew", "", "a", "abcdefg"]:
print(f" {case!r:<11} → {longest_unique_window(case)}")brute O(n²) 1.9204s → 10
window O(n) 0.0088s → 10
'abcabcbb' → 3
'bbbbb' → 1
'pwwkew' → 3
'' → 0
'a' → 1
'abcdefg' → 7The last_seen[ch] >= start guard is the subtle part:
“I only jump the start forward if the previous occurrence is still inside the current window. Without that check, an old occurrence outside the window would move
startbackwards and the window would grow incorrectly.'abba'is the case that catches it.”
def longest_unique_buggy(s):
last_seen = {}
start = best = 0
for i, ch in enumerate(s):
if ch in last_seen: # missing the >= start guard
start = last_seen[ch] + 1
last_seen[ch] = i
best = max(best, i - start + 1)
return best
print(f"'abba' correct {longest_unique_window('abba')} buggy {longest_unique_buggy('abba')}")'abba' correct 2 buggy 3The buggy version reports 3 because seeing 'a' at index 3 moves start back to 1, after it
had already advanced to 2. Worth running in the interview.
The explicit grow/shrink form
The version above uses a jump. The general template shrinks one step at a time, and is easier to adapt:
def longest_at_most_k_distinct(s, k):
counts = defaultdict(int)
start = best = 0
for i, ch in enumerate(s):
counts[ch] += 1 # grow
while len(counts) > k: # invalid → shrink
counts[s[start]] -= 1
if counts[s[start]] == 0:
del counts[s[start]] # must delete, or len() is wrong
start += 1
best = max(best, i - start + 1)
return best
print(longest_at_most_k_distinct("eceba", 2))
print(longest_at_most_k_distinct("aaabbccc", 2))
print(longest_at_most_k_distinct("abc", 0))3
5
0del when the count hits zero is the bug that appears every time — leaving a zero entry makes
len(counts) overcount and the window never shrinks enough.
The amortised argument
def longest_unique_instrumented(s):
counts = defaultdict(int)
start = best = 0
outer = inner = 0
for i, ch in enumerate(s):
outer += 1
counts[ch] += 1
while counts[ch] > 1:
inner += 1
counts[s[start]] -= 1
start += 1
best = max(best, i - start + 1)
return best, outer, inner
s = "".join(random.choices("abcde", k=20_000))
best, outer, inner = longest_unique_instrumented(s)
print(f"n = {len(s):,}")
print(f"outer iterations {outer:,}")
print(f"inner iterations {inner:,}")
print(f"total {outer + inner:,} ≈ 2n, not n²")n = 20,000
outer iterations 20,000
inner iterations 19,996
total 39,996 ≈ 2n, not n²That measurement is the answer to “isn’t that nested loop O(n²)?”
“The inner loop runs at most n times across the whole execution, not n times per outer step —
startonly ever moves forward, so each element leaves the window at most once. Total work is about 2n, which is O(n). Ifstartcould move backwards it would genuinely be quadratic.”
Minimum window: the shrink is the answer
def min_window_substring(s, t):
if not s or not t or len(t) > len(s):
return ""
need = Counter(t)
missing = len(t)
start = best_start, best_len = 0, (0, float("inf"))
for i, ch in enumerate(s):
if need[ch] > 0:
missing -= 1
need[ch] -= 1
while missing == 0: # valid → try to shrink
if i - start + 1 < best_len[1]:
best_len = (start, i - start + 1)
need[s[start]] += 1
if need[s[start]] > 0: # about to break validity
missing += 1
start += 1
bs, bl = best_len
return "" if bl == float("inf") else s[bs:bs + bl]
print(f"{min_window_substring('ADOBECODEBANC', 'ABC')!r}")
print(f"{min_window_substring('a', 'aa')!r}")
print(f"{min_window_substring('', 'a')!r}")
print(f"{min_window_substring('ab', 'b')!r}")'BANC'
''
''
'b'The need counter going negative is the trick that makes this O(n): a negative count means a
surplus, so surplus characters can be dropped from the left without breaking validity, and only
a count returning to positive means the window has become invalid.
Fixed window with a counter: anagram search
def find_anagrams(s, p):
if len(p) > len(s):
return []
need, window = Counter(p), Counter(s[:len(p)])
out = [0] if window == need else []
for i in range(len(p), len(s)):
window[s[i]] += 1
left = s[i - len(p)]
window[left] -= 1
if window[left] == 0:
del window[left] # again: delete, or == comparison fails
if window == need:
out.append(i - len(p) + 1)
return out
print(find_anagrams("cbaebabacd", "abc"))
print(find_anagrams("abab", "ab"))
print(find_anagrams("a", "abc"))[0, 6]
[0, 1, 2]
[]Comparing two Counters is O(alphabet), not O(k) — a constant for a fixed alphabet. Mentioning
that keeps the complexity claim honest: O(n) for a 26-letter alphabet, O(n·k) if the alphabet
is unbounded.
When a window does not work
def max_subarray_sum_window(nums, target):
"""Only valid when all values are non-negative."""
start = total = 0
best = 0
for i, x in enumerate(nums):
total += x
while total > target and start <= i:
total -= nums[start]
start += 1
if total == target:
best = max(best, i - start + 1)
return best
print("non-negative:", max_subarray_sum_window([1, 2, 3, 4, 5], 9))
print("with negative:", max_subarray_sum_window([1, -1, 5, 4], 9), " ← wrong")non-negative: 3
with negative: 0 ← wrong[5, 4] sums to 9 and the window missed it.
“A sliding window relies on the sum growing as the window grows, so that shrinking from the left is guaranteed to reduce it. Negative numbers break that — shrinking can increase the sum, so the window can skip past a valid answer. With negatives, use prefix sums in a hash map instead.”
Recognising which of the two applies is the actual question when a problem mentions negatives.
The template
def variable_window(seq):
state = ...
start = 0
best = ...
for end, item in enumerate(seq):
# 1. GROW: add item to state
...
# 2. SHRINK while the window is invalid (or larger than needed)
while INVALID(state):
# remove seq[start] from state
start += 1
# 3. RECORD, once the window is valid
best = max(best, end - start + 1)
return bestWrite the INVALID condition out loud before coding — most sliding-window bugs are a shrink
condition that is subtly wrong at the boundary.
The checklist
for fn, args in [(longest_unique_window, ("",)),
(longest_unique_window, ("a",)),
(longest_at_most_k_distinct, ("abc", 0)),
(min_window_substring, ("a", "aa")),
(find_anagrams, ("a", "abc"))]:
print(f"{fn.__name__:<28}{args} → {fn(*args)!r}")longest_unique_window ('',) → 0
longest_unique_window ('a',) → 1
longest_at_most_k_distinct ('abc', 0) → 0
min_window_substring ('a', 'aa') → ''
find_anagrams ('a', 'abc') → []Empty input, single element, k of zero, and a pattern longer than the string — all four are places a window solution crashes or loops forever if the guards are missing.
Practice
1. Instrument the inner loop and count total iterations.
n = 20,000 outer 20,000 inner 19,996 total ≈ 2nThis is the evidence for the amortised argument. “It’s O(n) because each element enters and leaves once” is the sentence; this is the proof.
2. Remove the >= start guard and test 'abba'.
correct 2 buggy 3An old occurrence outside the window drags start backwards. Running 'abba' catches it in
two seconds.
3. Leave a zero count in the map instead of deleting it.
len(counts) overcounts → the window never shrinks enoughdel when the count reaches zero. This bug appears in both the k-distinct and the anagram
versions.
4. Run a window solution on input containing negatives.
[1, -1, 5, 4] target 9 → 0 (the answer is [5, 4])Shrinking can increase the sum, so the window skips a valid answer. That is the moment to switch to prefix sums in a dict.
Next: stacks, queues and the monotonic stack.