Why Sliding Window?
⚡
From O(n^2) to O(n)
The sliding window technique transforms brute-force nested loops into a single pass through the data. It is one of the most frequently tested interview patterns.
🔎
When to Use It
Any time you need to find or compute something among contiguous subarrays or substrings of a given size (or satisfying a condition), sliding window is your go-to pattern.
📊
Interview Frequency
Sliding window problems appear in roughly 15-20% of coding interviews at top companies. Mastering this pattern covers a huge chunk of array/string questions.
Two Types of Sliding Windows
Fundamentals
1. Fixed-Size Window
Window size k is given. Slide it one element at a time.
Example: "Max sum subarray of size k"
Add the new element entering the window, remove the element leaving.
2. Variable-Size Window
Window size changes dynamically based on a condition.
Example: "Longest substring without repeating characters"
Expand right pointer, shrink left pointer when condition breaks.
Sliding Window Visualized
Fixed-Size Window Template
Template
Fixed Window Template (Python)
def fixed_window(arr, k):
# Step 1: Compute the first window
window_sum = sum(arr[:k])
best = window_sum
# Step 2: Slide the window
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k] # add new, remove old
best = max(best, window_sum)
return best
Classic Problem 1: Maximum Sum Subarray of Size K
Maximum Sum Subarray of Size K
def max_sum_subarray(arr, k):
if len(arr) < k:
return -1
# Sum of first window
window_sum = sum(arr[:k])
max_sum = window_sum
# Slide the window from index k to end
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, window_sum)
return max_sum
# Example
arr = [2, 1, 5, 1, 3, 2, 8]
k = 3
print(max_sum_subarray(arr, k)) # Output: 13 (subarray [3, 2, 8])
Step-by-Step Window State (k=3)
Window [2, 1, 5] -> sum = 8, max = 8
Window [1, 5, 1] -> sum = 7, max = 8
Window [5, 1, 3] -> sum = 9, max = 9
Window [1, 3, 2] -> sum = 6, max = 9
Window [3, 2, 8] -> sum = 13, max = 13 <-- answer
Variable-Size Window Template
Template
Variable Window Template (Python)
def variable_window(s):
left = 0
best = 0
state = {} # track window state (hash map, counter, etc.)
for right in range(len(s)):
# Expand: add s[right] to window state
state[s[right]] = state.get(s[right], 0) + 1
# Shrink: while condition is violated, move left
while /* window is invalid */:
state[s[left]] -= 1
if state[s[left]] == 0:
del state[s[left]]
left += 1
# Update best answer
best = max(best, right - left + 1)
return best
Classic Problem 2: Longest Substring Without Repeating Characters
Longest Substring Without Repeating Characters (LeetCode 3)
def length_of_longest_substring(s):
char_set = set()
left = 0
max_len = 0
for right in range(len(s)):
# Shrink window until no duplicate
while s[right] in char_set:
char_set.discard(s[left])
left += 1
char_set.add(s[right])
max_len = max(max_len, right - left + 1)
return max_len
# Example
print(length_of_longest_substring("abcabcbb")) # Output: 3 ("abc")
print(length_of_longest_substring("bbbbb")) # Output: 1 ("b")
print(length_of_longest_substring("pwwkew")) # Output: 3 ("wke")
Classic Problem 3: Minimum Window Substring (Hard)
Minimum Window Substring (LeetCode 76)
from collections import Counter
def min_window(s, t):
if not s or not t:
return ""
need = Counter(t)
missing = len(t) # chars still needed
left = start = 0
min_len = float('inf')
for right in range(len(s)):
# Expand: include s[right]
if need[s[right]] > 0:
missing -= 1
need[s[right]] -= 1
# Shrink: when all chars found, try to minimize
while missing == 0:
window_len = right - left + 1
if window_len < min_len:
min_len = window_len
start = left
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return s[start:start + min_len] if min_len != float('inf') else ""
# Example
print(min_window("ADOBECODEBANC", "ABC")) # Output: "BANC"
Classic Problem 4: Fruits Into Baskets (Max 2 Distinct Characters)
Fruits Into Baskets (LeetCode 904)
def total_fruit(fruits):
basket = {} # fruit_type -> count
left = 0
max_picked = 0
for right in range(len(fruits)):
basket[fruits[right]] = basket.get(fruits[right], 0) + 1
# More than 2 types? Shrink from left
while len(basket) > 2:
basket[fruits[left]] -= 1
if basket[fruits[left]] == 0:
del basket[fruits[left]]
left += 1
max_picked = max(max_picked, right - left + 1)
return max_picked
# Example
print(total_fruit([1,2,1])) # Output: 3
print(total_fruit([0,1,2,2])) # Output: 3 ([1,2,2])
print(total_fruit([1,2,3,2,2])) # Output: 4 ([2,3,2,2])
Step-by-Step: Longest Substring Without Repeating Characters
Input: "abcabcbb"
right=0: char='a', set={a}, window="a", len=1
right=1: char='b', set={a,b}, window="ab", len=2
right=2: char='c', set={a,b,c}, window="abc", len=3 <-- max
right=3: char='a', duplicate! shrink left until 'a' removed
set={b,c,a}, window="bca", len=3
right=4: char='b', duplicate! shrink left
set={c,a,b}, window="cab", len=3
...
Answer: 3
Pattern Recognition: When to Use Sliding Window
Decision Guide
Sliding Window Checklist
- The problem involves a contiguous subarray or substring
- You need to find max/min/count of something in a window
- The brute force involves two nested loops over the array
- Keywords: "subarray", "substring", "contiguous", "consecutive", "window of size k"
- The constraint can be checked by adding/removing one element at a time
Use Fixed Window When...
- ✅ Window size is given (k)
- ✅ "Maximum average subarray of length k"
- ✅ "All anagrams of pattern in string"
- ✅ "Max of all subarrays of size k"
Use Variable Window When...
- ✅ "Longest/shortest substring with condition"
- ✅ "Minimum window containing all characters"
- ✅ "Longest subarray with at most K distinct"
- ✅ "Smallest subarray with sum >= target"
Deep Dives
Advanced
Deep Dive 1: String Windows vs Array Windows
String windows typically use a hash map or frequency counter to track character counts. Array windows may use running sums, deques (for max/min), or other structures.
- Strings: Use
Counterordefaultdict(int)to track frequencies. Comparing against a "need" map is the standard pattern for substring matching. - Arrays: Running sum works for sum-based problems. For max/min in window, use a monotonic deque for O(n) instead of O(n*k).
Deep Dive 2: Optimization Tricks
- Early termination: If the remaining elements cannot beat the current best, stop.
- Hash map optimization: Instead of deleting keys with count 0, check
if count > 0to avoid overhead. - Two pointers as sliding window: Many two-pointer problems (e.g., container with most water) are variants of the sliding window concept.
- Monotonic deque: For "sliding window maximum" use a deque maintaining decreasing order -- gives O(n) overall.
Common Mistakes
Mistake #1: Off-by-One Errors
# WRONG: window size is k but loop starts at k-1
for i in range(k - 1, len(arr)):
window_sum += arr[i] - arr[i - k] # first iteration subtracts wrong element!
# CORRECT: compute first window separately, then slide from k
window_sum = sum(arr[:k])
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k]
Mistake #2: Forgetting to Shrink the Window
# WRONG: never shrinking -- window grows forever
for right in range(len(s)):
char_set.add(s[right])
max_len = max(max_len, right - left + 1)
# Missing: while s[right] in char_set: ... left += 1
# CORRECT: always check and shrink when condition is violated
for right in range(len(s)):
while s[right] in char_set:
char_set.discard(s[left])
left += 1
char_set.add(s[right])
max_len = max(max_len, right - left + 1)
Practice Problems
Practice Time!
E
Easy: Maximum Average Subarray I (LeetCode 643)
Given an array of n integers, find the contiguous subarray of length k that has the maximum average value.
Hint
Fixed window of size k. Track running sum, divide by k at the end.
M
Medium: Longest Repeating Character Replacement (LeetCode 424)
Given a string and integer k, find the length of the longest substring where you can replace at most k characters to make all characters the same.
Hint
Variable window. Track the count of the most frequent character. Window is valid when window_size - max_freq <= k.
H
Hard: Substring with Concatenation of All Words (LeetCode 30)
Find all starting indices where the concatenation of all words in a list exactly matches a substring.
Hint
Fixed window of size len(words) * len(words[0]). Use a word-level sliding window with two hash maps.
Quick Reference Guide
Key Takeaways
- Fixed window = given size k, slide one element at a time. O(n).
- Variable window = expand right, shrink left when condition breaks. O(n).
- Always ask: "Is this a contiguous subarray/substring problem?" If yes, try sliding window first.
Related Topics
Time Complexities
- Fixed Window: O(n)
- Variable Window: O(n) -- each element added/removed at most once
- Brute Force (nested loops): O(n*k) or O(n^2)