Sliding Window LeetCode Pattern Guide — Fixed and Variable Window Templates
A template-driven guide to fixed and variable sliding window problems, covering invariants, frequency maps, at-most-K counting, replacement tricks, deques, and common traps.
Sliding Window LeetCode Pattern Guide — Fixed and Variable Window Templates
A sliding window LeetCode pattern guide should help you decide when two pointers are enough, what invariant the window maintains, and exactly when to expand or shrink. Fixed-window problems ask for the best value over every length-k range. Variable-window problems ask for the longest, shortest, or count of subarrays/substrings that satisfy a constraint. The code is short only after the invariant is clear.
This guide gives templates, recognition rules, traps, and interview narration for fixed and variable window problems.
Sliding window LeetCode pattern guide: when to use it
Sliding window works when you are scanning a contiguous segment of an array or string and can update the answer as the segment moves. The important word is contiguous. Subsequences are not sliding-window problems because they can skip elements. Sorting problems are usually not sliding-window problems unless the sort creates a meaningful contiguous order.
Clues in the prompt:
- subarray or substring
- longest, shortest, maximum, minimum, or count over contiguous ranges
- at most K distinct characters
- no repeating characters
- sum at least target with positive numbers
- average of every window of size K
- permutation in string or anagram indices
- replace at most K characters
Sliding window usually needs a property that changes predictably when you move left or right. If all numbers are positive, expanding increases sum and shrinking decreases sum. If characters are counted, expanding increments a frequency and shrinking decrements it. If negative numbers appear in a sum problem, a basic sliding window may fail because sum is no longer monotonic.
A good interview opener: "This is a contiguous-range problem, so I will maintain a window [left, right] and an invariant that tells me when the window is valid. Then I can update the answer without rechecking the whole window."
Fixed window template
Use a fixed window when the length is given: size k, every group of k, average of k, maximum sum of k, or count of matches in a length equal to another string.
Template:
def fixed_window(nums, k):
window = 0
best = float('-inf')
for right, x in enumerate(nums):
window += x
if right >= k:
window -= nums[right - k]
if right >= k - 1:
best = max(best, window)
return bestThe invariant: after removing the old element, window represents the last k elements ending at right. The update happens only once the first full window exists.
Example: maximum average subarray of length k is the same template with best / k at the end. Counting vowels in every length-k substring uses a boolean contribution instead of numeric sum. Checking if a string contains a permutation of another string uses a fixed window whose length equals the pattern length, plus character counts.
Fixed-window mistakes:
- updating the answer before the window reaches size
k - removing the left element too late
- using
right - k + 1incorrectly - recomputing sum/count from scratch for every window
- forgetting edge cases when
k > len(nums)ork == 0
Variable window template: longest valid window
Use variable window when you want the longest substring/subarray satisfying a condition: no repeats, at most K distinct, at most K replacements, sum <= target with positive numbers.
Template:
def longest_valid(s):
left = 0
best = 0
state = {}
for right, ch in enumerate(s):
add ch to state
while window is invalid:
remove s[left] from state
left += 1
best = max(best, right - left + 1)
return bestThe invariant after the while loop: the current window is valid. Because it is valid, it can update the longest answer.
For Longest Substring Without Repeating Characters:
def length_of_longest_substring(s):
left = 0
seen = set()
best = 0
for right, ch in enumerate(s):
while ch in seen:
seen.remove(s[left])
left += 1
seen.add(ch)
best = max(best, right - left + 1)
return bestFor Longest Substring with At Most K Distinct Characters:
from collections import defaultdict
def longest_k_distinct(s, k):
left = 0
count = defaultdict(int)
best = 0
for right, ch in enumerate(s):
count[ch] += 1
while len(count) > k:
old = s[left]
count[old] -= 1
if count[old] == 0:
del count[old]
left += 1
best = max(best, right - left + 1)
return bestIn both cases, every character enters and leaves the window at most once, so time is O(n).
Variable window template: shortest valid window
For shortest-window problems, the order flips. You expand until the window becomes valid, then shrink while it remains valid, updating the answer during shrink.
Template:
def shortest_valid(arr):
left = 0
best = float('inf')
state = initialize
for right, x in enumerate(arr):
add x to state
while window is valid:
best = min(best, right - left + 1)
remove arr[left] from state
left += 1
return best if best != float('inf') else 0Example: minimum size subarray sum with positive numbers.
def min_subarray_len(target, nums):
left = 0
total = 0
best = float('inf')
for right, x in enumerate(nums):
total += x
while total >= target:
best = min(best, right - left + 1)
total -= nums[left]
left += 1
return 0 if best == float('inf') else bestWhy positivity matters: if numbers can be negative, shrinking may increase the sum or expanding may decrease it. Then this invariant breaks and you may need prefix sums plus a hashmap or monotonic deque.
Frequency maps and anagram windows
String window problems often use frequency maps. The trick is to avoid comparing full dictionaries on every step when the alphabet is large. Keep a matches count or a need count.
For finding anagrams of p in s, use a fixed window of length len(p). A straightforward version is acceptable for lowercase English letters:
from collections import Counter
def find_anagrams(s, p):
need = Counter(p)
window = Counter()
ans = []
k = len(p)
for right, ch in enumerate(s):
window[ch] += 1
if right >= k:
old = s[right - k]
window[old] -= 1
if window[old] == 0:
del window[old]
if right >= k - 1 and window == need:
ans.append(right - k + 1)
return ansFor interviews, explain the tradeoff: full counter comparison is fine when the alphabet is fixed and small; a matches-based implementation is better when you need strict O(n) with a larger character set.
For minimum window substring, maintain how many required characters are currently satisfied:
need[c]= required counthave[c]= current countformed= number of characters wherehave[c] >= need[c]- valid when
formed == len(need)
This is a shortest-valid-window problem, not a longest-valid-window problem.
The "at most K" counting trick
Some LeetCode problems ask for the number of subarrays with exactly K distinct values. Counting exact windows directly is awkward. The clean trick:
exactly(K) = at_most(K) - at_most(K - 1)
The at_most helper counts all valid subarrays ending at each right.
from collections import defaultdict
def subarrays_with_at_most_k(nums, k):
if k < 0:
return 0
left = 0
count = defaultdict(int)
ans = 0
for right, x in enumerate(nums):
count[x] += 1
while len(count) > k:
old = nums[left]
count[old] -= 1
if count[old] == 0:
del count[old]
left += 1
ans += right - left + 1
return ans
def subarrays_with_exactly_k(nums, k):
return subarrays_with_at_most_k(nums, k) - subarrays_with_at_most_k(nums, k - 1)Why right - left + 1? Once the window [left, right] is valid for at most K, every subarray ending at right and starting between left and right is also valid. That single line is the insight.
Replacement problems and stale max counts
The classic example is Longest Repeating Character Replacement: choose at most k characters to replace so the window becomes all one character.
Condition:
window_length - max_frequency <= k
Template:
from collections import defaultdict
def character_replacement(s, k):
left = 0
count = defaultdict(int)
max_freq = 0
best = 0
for right, ch in enumerate(s):
count[ch] += 1
max_freq = max(max_freq, count[ch])
while (right - left + 1) - max_freq > k:
count[s[left]] -= 1
left += 1
best = max(best, right - left + 1)
return bestA subtle point: max_freq can be stale after shrinking. That is okay for this longest-window problem because a stale high value may delay shrinking, but it will not cause a too-large answer to be accepted incorrectly; the best length is still found when a real max frequency supported it. If you are uncomfortable explaining that, recompute max_freq in the loop for a small fixed alphabet. Correctness clarity beats cleverness.
Monotonic deque: sliding window maximum
Some sliding-window problems need the best element inside each fixed window, not just a sum or count. Use a monotonic deque.
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, values decreasing
ans = []
for right, x in enumerate(nums):
while dq and dq[0] <= right - k:
dq.popleft()
while dq and nums[dq[-1]] <= x:
dq.pop()
dq.append(right)
if right >= k - 1:
ans.append(nums[dq[0]])
return ansThe deque stores candidates, not the whole window. Old indices leave from the front. Smaller values behind the new value are removed because they can never become maximum while the new value is in the window.
This is still a sliding-window pattern because each index enters and leaves the deque at most once.
When sliding window is the wrong tool
Part of mastering the pattern is knowing when not to use it. If the prompt says subsequence, graph path, arbitrary reorder, or non-contiguous selection, sliding window is usually the wrong frame. If the sum condition includes negative numbers, test the monotonic assumption before committing. A window that becomes valid at right may become invalid or more valid in surprising ways after removing a negative number.
Common alternatives:
- Prefix sum + hashmap for subarray sum equals K with negative numbers.
- Prefix sum + monotonic deque for shortest subarray at least K when negatives exist.
- Dynamic programming for subsequences where elements can be skipped.
- Sorting + two pointers for pair or triplet problems after order no longer represents original contiguity.
A useful interview sentence is: "I would use sliding window only if moving the left pointer predictably restores validity. If negatives or non-contiguous choices break that, I will switch to prefix sums or DP." That shows judgment, not just template recall.
Common traps
Trap: Using sliding window when negatives break monotonicity. For shortest sum at least target, basic sliding window requires positive numbers. With negatives, use prefix sums and different tools.
Trap: Not stating the invariant. Code with two pointers is not automatically sliding window. Say what makes the window valid or invalid.
Trap: Updating answer in the wrong place. For longest valid windows, update after shrinking invalid state. For shortest valid windows, update inside the while-valid shrink loop.
Trap: Confusing exact K and at most K. Exact K is often easier as at most K minus at most K minus one.
Trap: Deleting frequency keys too late. If a count reaches zero but remains in the map, len(count) becomes wrong.
Trap: Forgetting window length. In Python, the inclusive window length is right - left + 1.
Interview checklist
Before coding, answer these out loud:
- Is the segment contiguous?
- Is the window length fixed or variable?
- What state do I need: sum, count map, max frequency, deque, or matched requirements?
- What makes the window invalid or valid?
- Do I update best before or after shrinking?
- Does each pointer move only forward?
- Do constraints allow negative numbers that break the approach?
- What is the time and space complexity?
A concise closing explanation: "The right pointer expands the candidate window, the left pointer restores the invariant, and every element is added and removed at most once, so the scan is linear." If you can say that and your invariant is correct, sliding window problems become much less mysterious.
Related guides
- DFS LeetCode Pattern Guide — Recursion Templates and Grid/Graph Problems — A DFS LeetCode pattern guide with recursion templates, visited-set rules, grid and graph examples, backtracking structure, complexity notes, and interview pitfalls.
- Dynamic Programming LeetCode Pattern Guide — Knapsack, LIS, and Interval DP Templates — A pattern-first DP guide for LeetCode interviews, with recognition rules, knapsack, LIS, interval DP templates, loop-order traps, and interview narration.
- Backtracking LeetCode Pattern Guide — Permutations, Combinations, and Subsets — A practical backtracking LeetCode pattern guide with templates, decision rules, duplicate-handling tricks, pruning advice, and interview talk tracks for permutations, combinations, subsets, and constraint problems.
- BFS LeetCode Pattern Guide — Shortest-Path, Level-Order, and Multi-Source — A BFS LeetCode pattern guide for recognizing queue-based problems, implementing level-order traversal, solving unweighted shortest paths, using multi-source BFS, and avoiding common visited-state bugs.
- Binary Search LeetCode Pattern Guide — Bounds, Rotated Arrays, and Search-on-Answer — A binary search LeetCode pattern guide for exact search, lower/upper bounds, rotated arrays, and search-on-answer problems. Includes invariants, templates, traps, and interview-ready explanations.