Pattern 05 · Arrays & Strings
Sliding Window
Maintain a contiguous window over the input and slide it forward, updating state incrementally instead of recalculating from scratch. The pattern that turns O(n·k) brute force into one clean O(n) pass.
time O(n)space O(k)variants fixed · dynamicpractice 12 problems
01 core concept
Stop recomputing what you already know
Brute force re-sums every subarray: O(n · k). The window keeps a running
state and does O(1) work per step — subtract the element leaving on the left,
add the element arriving on the right.
step 1 / 6walkthrough — max sum of k = 3 consecutive elements
sum —
best —
Goal: the maximum sum of any 3 consecutive elements. Brute force would re-sum all 4 windows — 12 additions. We'll do it in 6.
02 two types
Fixed vs. dynamic windows
Type AFixed size
The window has a predetermined, constant size k. Slide one step at a time;
record an answer whenever the window is full.
Type BDynamic size
The window expands on the right and contracts on the left based on a condition. Used for "longest substring such that…" and "shortest subarray such that…" problems.
step 1 / 12walkthrough — shortest subarray with sum ≥ 7
sum 2
best len ∞
sum = 2 < 7 → expand R. The right pointer does the exploring.
The shrink rule
For longest-window problems, shrink only while invalid.
For shortest-window problems, shrink while still valid (recording each time).
Getting this backwards is the #1 sliding-window bug.
03 recognition
When to reach for it
- The problem asks about a contiguous subarray or substring.
- You see "longest / shortest / max / min / count" + "substring / subarray" + a constraint.
- A brute-force answer would re-examine overlapping ranges.
- The constraint is monotonic: growing the window only makes it "more" (bigger sum, more distinct chars) and shrinking makes it "less."
When NOT to use it
Non-contiguous subsequences → DP. Arrays with negative numbers in sum problems →
the shrink logic breaks (adding an element may decrease the sum); use prefix sums + hashmap instead.
04 templates
The three templates to memorize
T1Fixed window
fixed_window.pypython
def max_sum_fixed(nums, k):
window_sum = 0
best = float("-inf")
for right in range(len(nums)):
window_sum += nums[right] # 1. add the arriving element
if right >= k: # 2. window too big -> evict left
window_sum -= nums[right - k]
if right >= k - 1: # 3. window full -> record
best = max(best, window_sum)
return bestT2Dynamic — longest valid window
longest_no_repeat.py — LC 3python
def longest_no_repeat(s):
seen = {} # char -> latest index
left = 0
best = 0
for right, ch in enumerate(s):
if ch in seen and seen[ch] >= left:
left = seen[ch] + 1 # jump left past the duplicate
seen[ch] = right
best = max(best, right - left + 1) # window is ALWAYS valid here
return bestT3Dynamic — shortest valid window
min_subarray_sum.py — LC 209python
def min_subarray_len(target, nums):
left = 0
window_sum = 0
best = float("inf")
for right in range(len(nums)):
window_sum += nums[right]
while window_sum >= target: # shrink WHILE valid
best = min(best, right - left + 1)
window_sum -= nums[left]
left += 1
return best if best != float("inf") else 0Why it's O(n) despite the nested while
Each element is added once and removed at most once — left never moves backward.
Total: at most 2n pointer moves. The nested loop is amortized O(1) per step.
05 common mistakes
Where windows go wrong
Mistake 1 — ghost keys in the counter
When shrinking, decrementing a count isn't enough for distinct-character problems —
len(char_count) stays wrong until you del zero-count keys.
the fixpython
# WRONG: leaves ghost keys, len(char_count) lies
char_count[leaving] -= 1
# RIGHT: clean up zero-count keys
char_count[leaving] -= 1
if char_count[leaving] == 0:
del char_count[leaving]Mistake 2 — off-by-one on "window full"
A fixed window is first full at right == k - 1, not k.
And window size is right - left + 1, not right - left.
Mistake 3 — shrinking in the wrong direction
Longest → shrink only when invalid. Shortest → shrink while valid. Say it out loud in the interview.
Mistake 4 — O(k) validity checks every step
Comparing two Counter objects each iteration is O(k). Use the
have / need integer trick (LC 76, 438) for O(1) checks.
Mistake 5 — negative numbers
Sum-based shrinking assumes adding elements grows the sum. Negatives break the
monotonicity — switch to prefix sums.
10 practice
Practice ladder
In this order — easiest first. Tick each one as you solve it, and re-solve anything that took more than 25 minutes two days later.
12 problems
mediumLC 3
Dynamic window + dict of last-seen indices. Template T2.
mediumLC 424
Dynamic + max-frequency trick (window never shrinks below best).
hardLC 30
Fixed window at the word level, not the character level.