What you will learn
- Distinguish fixed-size from variable-size sliding windows
- Implement the expand/contract template for variable windows
- Solve max subarray sum, longest substring without repeating characters, and minimum window substring
Why this matters
Sliding window eliminates redundant computation by reusing previous results as you shift through a sequence. It's the go-to technique for contiguous subarray and substring problems and appears in nearly every interview question bank.
The core idea
Maintain a "window" defined by two indices [left, right]. Expand the window by advancing right, and contract it by advancing left. Track a running result (sum, count, character set) so each expansion or contraction is O(1) work.
Fixed-size window
When the window size k is given, slide it across in one pass.
def max_sum_subarray(nums, k):
"""Maximum sum of any contiguous subarray of size k."""
window_sum = sum(nums[:k])
best = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k] # add right, drop left
best = max(best, window_sum)
return bestTime: O(n). Space: O(1).
Variable-size window template
When the window size is unknown, expand until a condition breaks, then contract until it's restored.
def longest_substring_no_repeat(s):
"""LeetCode 3: Longest Substring Without Repeating Characters."""
seen = {}
left = 0
best = 0
for right, char in enumerate(s):
if char in seen and seen[char] >= left:
left = seen[char] + 1
seen[char] = right
best = max(best, right - left + 1)
return bestTime: O(n) — each character is visited at most twice (once by right, once by left).
Space: O(min(n, alphabet size)).
Variable window: Minimum Window Substring
from collections import Counter
def min_window(s, t):
"""LeetCode 76: Minimum Window Substring."""
need = Counter(t)
missing = len(t)
left = 0
start, end = 0, float('inf')
for right, char in enumerate(s):
if need[char] > 0:
missing -= 1
need[char] -= 1
while missing == 0: # window contains all of t
if right - left < end - start:
start, end = left, right
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return s[start:end + 1] if end < float('inf') else ""When to reach for sliding window
| Signal | Window type |
|---|---|
| "Subarray of size k" or "k consecutive elements" | Fixed |
| "Longest/shortest subarray with condition X" | Variable |
| "Substring containing all characters of T" | Variable with frequency map |
| "At most k distinct elements" | Variable with counter |
Quick quiz
Q: You need the maximum sum of any contiguous subarray of size k. A brute-force approach recalculates the sum from scratch for each window. What does the sliding window approach save?
How to explain it in an interview
"I'd maintain a running sum. Start with the sum of the first k elements. For each new position, add the incoming element and subtract the outgoing one. This way each step is O(1) and the whole pass is O(n). For variable-size windows I use the expand-then-contract template: grow the right boundary until a condition breaks, then shrink from the left until it's restored, tracking the best answer throughout."