The short answer
Sliding window turns O(n^2) brute-force problems into O(n) scans. The ten patterns that cover roughly 85 percent of interview problems: fixed window, variable window shrink-on-condition, longest substring without repeats, longest with k distinct, minimum window substring, maximum sum subarray, permutation in string, anagrams in string, two-pointer merge, and monotonic deque for window maximum.
I spent three weeks grinding sliding window problems before a FAANG interview. The pattern recognition is what matters. Once you can name which of these ten patterns a problem belongs to, the implementation drops out in minutes.
This guide walks each pattern with a clean Python implementation, the time complexity, and the LeetCode problem that defines it. No fluff. Study each one until you can write it from scratch without looking.
Pattern 1: Fixed-size window
The simplest sliding window. You compute an aggregate over every contiguous subarray of size k. Classic problem: maximum sum of a subarray of size k.
def max_sum_k(nums, k):
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k]
best = max(best, window)
return bestTime O(n), space O(1). The trick is adding the new element and subtracting the one that leaves the window, instead of re-summing.
Pattern 2: Variable window, shrink on condition
Window grows by moving right. Window shrinks by moving left when some constraint breaks. Problem: smallest subarray with sum at least target.
def min_subarray(target, nums):
left, total, best = 0, 0, float('inf')
for right in range(len(nums)):
total += nums[right]
while total >= target:
best = min(best, right - left + 1)
total -= nums[left]
left += 1
return 0 if best == float('inf') else bestThis template covers maybe a third of sliding window problems. Memorize it.
Pattern 3: Longest substring without repeating characters
A hash set tracks what is in the window. If the incoming character is already there, shrink from the left until it is not.
def length_of_longest(s):
seen = set()
left, best = 0, 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 bestLeetCode 3. Appears verbatim in dozens of interviews every year.
Pattern 4: Longest substring with at most k distinct characters
Dictionary counts occurrences. When the count of distinct keys exceeds k, shrink until the invariant holds.
def longest_k_distinct(s, k):
counts = {}
left, best = 0, 0
for right, ch in enumerate(s):
counts[ch] = counts.get(ch, 0) + 1
while len(counts) > k:
counts[s[left]] -= 1
if counts[s[left]] == 0:
del counts[s[left]]
left += 1
best = max(best, right - left + 1)
return bestVariant: longest with exactly k distinct = f(k) – f(k-1). This trick appears often.
Pattern 5: Minimum window substring
You need every character of t inside the window, counted. Track how many required characters are satisfied, then shrink while the requirement still holds.
from collections import Counter
def min_window(s, t):
need = Counter(t)
missing = len(t)
left = start = end = 0
for right, ch in enumerate(s, 1):
if need[ch] > 0:
missing -= 1
need[ch] -= 1
if missing == 0:
while need[s[left]] < 0:
need[s[left]] += 1
left += 1
if end == 0 or right - left < end - start:
start, end = left, right
need[s[left]] += 1
missing += 1
left += 1
return s[start:end]LeetCode 76. Hardest of the standard patterns but mechanical once you understand the invariant.
Pattern 6: Maximum sum subarray of size k on circular array
Concatenate the array with itself conceptually, then run fixed-size window up to index 2n. Add a check so the window does not exceed n in span.
Alternative: compute max subarray and min subarray with Kadane, then return max(regular_max, total_sum - min_subarray). This handles the wrap case elegantly.
Pattern 7: Permutation in string
Does s2 contain any permutation of s1 as a substring? Count characters in s1. Slide a fixed window of size len(s1) across s2, comparing character counts.
def check_inclusion(s1, s2):
need = Counter(s1)
window = Counter(s2[:len(s1)])
if window == need:
return True
for i in range(len(s1), len(s2)):
window[s2[i]] += 1
window[s2[i - len(s1)]] -= 1
if window[s2[i - len(s1)]] == 0:
del window[s2[i - len(s1)]]
if window == need:
return True
return FalsePattern 8: Find all anagrams in a string
Same engine as Pattern 7, but instead of returning on first match, collect every index where the window matches the target count. LeetCode 438.
Pattern 9: Two-pointer on sorted inputs
Not strictly sliding window, but the same discipline. Two sum on a sorted array: left and right pointers converge based on the sum relative to target.
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target:
return [left, right]
if s < target:
left += 1
else:
right -= 1Pattern 10: Monotonic deque for sliding window maximum
The max of every size-k window. Naive is O(nk). A deque keeping indices in decreasing order of values gives O(n). Pop from the back while the back value is less than the new one, pop from the front if it is outside the window.
from collections import deque
def max_sliding_window(nums, k):
dq, out = deque(), []
for i, n in enumerate(nums):
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
out.append(nums[dq[0]])
return outLeetCode 239. One of the most asked hard problems in system design-adjacent interviews.
How to practice these
Do not try to memorize code. Write each pattern from scratch five times across a week. Then find three LeetCode problems that use each pattern and solve them cold. Patterns 2, 3, 5, and 10 cover the most interview surface.
Common pitfalls to avoid
- Resetting counters or sets inside the loop by accident instead of maintaining them across iterations.
- Updating the answer in the wrong place: compute the candidate length after both pointers have moved, not during the shrink step.
- Off-by-one on the window size: right - left + 1 for inclusive bounds, right - left for exclusive.
- Forgetting that the inner while loop total work across the whole scan is still O(n), not O(n^2); do not panic at the nested structure.
- Using a set when the problem needs a count (a character that appears twice in the target needs to appear twice in the window).
When stuck on a sliding window problem, write out the invariant first: what must be true about the window for the current answer to be valid? The code then almost writes itself from the invariant.
Frequently asked questions
How do I recognize a sliding window problem in an interview?
Look for keywords like "contiguous subarray," "substring," "window of size k," or "longest/shortest sequence satisfying a condition." If the input is an array or string and the answer is some subsequence of adjacent elements, try sliding window first.
What is the time complexity of the standard sliding window?
O(n). Each element is added once (right pointer) and removed once (left pointer). Even though there are two nested loops in some templates, the inner loop total work across all iterations is bounded by n.
When should I use a hash map versus a set in the window?
Set when you only need presence or absence. Hash map when you need to count occurrences or compare against a required count. Most medium-level problems need a hash map; easy ones often work with a set.
Is sliding window ever the wrong approach?
Yes. If the problem allows non-contiguous subsets, sliding window will not work. If the array contains negative numbers and you are tracking sum-based conditions, shrinking the window may not guarantee correctness. Prefix sums or DP take over there.
How many of these ten patterns are enough for FAANG interviews?
All ten, but patterns 2, 3, 5, 7, and 10 cover roughly 80 percent of the sliding window problems you will actually see. Master those first, then add the others as time allows.
What is the difference between sliding window and two pointers?
Sliding window maintains a contiguous range and processes elements inside it. Two pointers can move independently, often converging on a sorted array. Every sliding window is technically a two-pointer pattern, but not every two-pointer problem is sliding window.
