Loading learning content...
You now possess the mechanical knowledge of sliding windows—both fixed and variable-size variants. But technical interviews and real-world problems rarely announce themselves as "sliding window problems." Your challenge is recognition: seeing the underlying pattern beneath the surface.
This page bridges the gap between knowing the technique and applying it instinctively. We'll explore classic problems that have become benchmarks for sliding window mastery, analyze why certain problems fit the pattern while similar-looking ones don't, and develop heuristics for rapid recognition.
By the end of this page, you will master several classic sliding window problems, understand the connection between sliding window and Kadane's algorithm, learn to distinguish sliding window problems from imposters, and develop a mental checklist for pattern recognition.
Let's start with the canonical fixed-size sliding window problem. This is the problem you should visualize when you see "fixed window" patterns.
Problem Statement:
Given an array of integers and a number k, find the maximum sum of any contiguous subarray of size exactly k.
This problem is the purest expression of fixed-size sliding window. No tricks, no additional constraints—just slide and track.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253
def max_sum_subarray_k(arr, k): """ Maximum sum of any k consecutive elements. Time: O(n), Space: O(1) Template application: - State: window_sum - Update on entry: add new element - Update on exit: subtract departing element - Result extraction: track maximum """ n = len(arr) if n < k or k <= 0: return None # Phase 1: Build initial window window_sum = sum(arr[:k]) max_sum = window_sum # Phase 2: Slide for i in range(k, n): window_sum += arr[i] - arr[i - k] max_sum = max(max_sum, window_sum) return max_sum def max_sum_subarray_k_with_indices(arr, k): """ Extended version that also returns the starting index of the maximum sum subarray. """ n = len(arr) if n < k or k <= 0: return None, None window_sum = sum(arr[:k]) max_sum = window_sum max_start = 0 for i in range(k, n): window_sum += arr[i] - arr[i - k] if window_sum > max_sum: max_sum = window_sum max_start = i - k + 1 # Start of current window return max_sum, max_start # Example usage:# arr = [2, 1, 5, 1, 3, 2], k = 3# Result: 9, starting at index 2 (subarray [5, 1, 3])When encountering any fixed-size sliding window problem, mentally map it to this example. Ask: 'What am I tracking instead of sum? How do I update on entry? On exit?' Most fixed-size problems are variations of this structure.
A related but distinct problem is finding the maximum sum subarray of any size—not a fixed size. This is the famous Maximum Subarray Problem, solved classically by Kadane's Algorithm.
Problem Statement: Given an array of integers (possibly negative), find the contiguous subarray with the largest sum.
Why This Isn't Traditional Sliding Window:
At first glance, this seems like it should be a variable-size sliding window. But there's a subtle problem: with negative numbers, the constraint isn't monotonic. Adding a positive number helps; adding a negative number hurts. There's no clear "shrink when invalid" condition.
Kadane's Insight:
Instead of thinking about windows, think about decisions at each position. At each index, you decide: should I extend the previous subarray or start fresh here?
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
def max_subarray_kadane(nums): """ Kadane's Algorithm for maximum subarray sum. Time: O(n), Space: O(1) Key insight: At each position i, ask: "Is it better to extend the subarray ending at i-1, or start a new subarray at i?" If current_sum + nums[i] < nums[i], then the cumulative sum up to i-1 was negative—we're better off starting fresh. """ if not nums: return 0 current_sum = nums[0] # Best sum ending at current position max_sum = nums[0] # Best sum seen overall for i in range(1, len(nums)): # Extend previous subarray or start new one? current_sum = max(current_sum + nums[i], nums[i]) max_sum = max(max_sum, current_sum) return max_sum def max_subarray_with_indices(nums): """ Extended version returning the subarray boundaries. """ if not nums: return 0, -1, -1 current_sum = nums[0] max_sum = nums[0] start = 0 # Start of current subarray max_start = 0 # Start of max subarray max_end = 0 # End of max subarray for i in range(1, len(nums)): if current_sum + nums[i] < nums[i]: # Start fresh at i current_sum = nums[i] start = i else: # Extend previous subarray current_sum += nums[i] if current_sum > max_sum: max_sum = current_sum max_start = start max_end = i return max_sum, max_start, max_end # Trace: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]## i=0: current=-2, max=-2# i=1: max(-2+1, 1)=1, start fresh at 1# current=1, max=1# i=2: max(1-3, -3)=-2, extend# current=-2, max=1# i=3: max(-2+4, 4)=4, start fresh at 3# current=4, max=4# i=4: max(4-1, -1)=3, extend# current=3, max=4# i=5: max(3+2, 2)=5, extend# current=5, max=5# i=6: max(5+1, 1)=6, extend# current=6, max=6# i=7: max(6-5, -5)=1, extend# current=1, max=6# i=8: max(1+4, 4)=5, extend# current=5, max=6## Result: 6 (subarray [4, -1, 2, 1])Sliding window needs a monotonic constraint: 'if the window is invalid, shrinking helps.' With negatives and no fixed size, there's no clear invalidity condition. Kadane works because it reformulates the problem as a local decision (extend vs restart) rather than a window maintenance problem.
Connection to Sliding Window:
Kadane's algorithm can be viewed through a sliding window lens if you squint:
But this is a degenerate case where the left pointer can jump, not just increment. Traditional sliding window constrains left to move only forward, one step at a time. Kadane breaks this constraint for efficiency.
When to Use Which:
| Problem | Approach |
|---|---|
| Max sum of exactly k elements | Fixed sliding window |
| Max sum of any contiguous subarray | Kadane's algorithm |
| Max sum of subarray with at most k elements | Kadane's with constraint |
| Max sum of subarray with sum ≤ target | Variable sliding window (positives only) |
A constellation of classic problems revolves around finding the longest substring satisfying some constraint. These are quintessential variable-size sliding window problems.
| Problem | Constraint | State to Track | Shrink When |
|---|---|---|---|
| No repeating characters | All chars unique | Char set or index map | Duplicate found |
| At most k distinct | ≤ k unique chars | Freq map + distinct count | Distinct > k |
| At most k 0s (in binary) | ≤ k zeros | Zero count | Zeros > k |
| Same character after k flips | ≤ k non-majority chars | Max freq in window | Size - max_freq > k |
| Containing all chars of T | T ⊆ window | Char freq + formed count | Never (shortest problem) |
Pattern: Longest Substring with At Most K [Something]
This pattern is so common it deserves explicit attention. The template is:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354
def longest_substring_at_most_k(s, k, count_what): """ Generic template for 'longest substring with at most k X' problems. count_what: a function that updates the count we're limiting """ left = 0 count = 0 # Count of the limited resource max_length = 0 for right, char in enumerate(s): # Add right character to window count += count_what(char, 'add') # Shrink while constraint violated while count > k: count += count_what(s[left], 'remove') left += 1 # Window is valid, update maximum max_length = max(max_length, right - left + 1) return max_length # Concrete example: Longest substring with at most k zerosdef longest_ones_with_k_flips(nums, k): """ Given binary array, find longest subarray of 1s if you can flip at most k 0s to 1s. Equivalently: longest subarray with at most k zeros. """ left = 0 zeros = 0 max_length = 0 for right in range(len(nums)): if nums[right] == 0: zeros += 1 while zeros > k: if nums[left] == 0: zeros -= 1 left += 1 max_length = max(max_length, right - left + 1) return max_length # Example: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2# Max length = 6 (subarray starting at index 4, flipping zeros at 4,5# or starting at index 5, flipping zeros at 5,10)Problems about 'replacing at most k elements' are often sliding window in disguise. 'Longest subarray of X after k replacements' means 'longest subarray with at most k non-X elements.' Reframe the problem around what you're counting.
Another important class involves finding substrings that contain required elements. These are typically "shortest valid" problems.
Classic: Find All Anagrams We covered this in fixed-size windows—the window size is fixed to len(pattern).
Classic: Minimum Window Containing All Characters We covered this in variable-size windows—the "shortest valid" archetype.
Variant: Permutation in String
Check if string s2 contains a permutation of s1.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859
def check_inclusion(s1, s2): """ Return True if s2 contains a permutation of s1. This is a fixed-size sliding window problem: window size = len(s1). We're looking for any window in s2 with the same character frequency as s1. """ len1, len2 = len(s1), len(s2) if len1 > len2: return False # Frequency tracking s1_freq = [0] * 26 window_freq = [0] * 26 def idx(c): return ord(c) - ord('a') # Build s1 frequency for c in s1: s1_freq[idx(c)] += 1 # Track matches (chars with matching frequency) matches = 0 for i in range(26): if s1_freq[i] == 0: # Both are 0 matches += 1 for i, c in enumerate(s2): # Add entering character ci = idx(c) if window_freq[ci] == s1_freq[ci]: matches -= 1 # Will no longer match window_freq[ci] += 1 if window_freq[ci] == s1_freq[ci]: matches += 1 # Now matches # Remove leaving character (if window full) if i >= len1: leaving = s2[i - len1] li = idx(leaving) if window_freq[li] == s1_freq[li]: matches -= 1 window_freq[li] -= 1 if window_freq[li] == s1_freq[li]: matches += 1 # Check if all 26 characters match if matches == 26: return True return False # This is more efficient than comparing entire frequency arrays# because we only update the match status of changed characters.Substring with Concatenation of All Words
A more complex variant: find all starting indices where a concatenation of all given words (in any order) starts.
This is still sliding window, but the "element" is a word (of fixed length), not a character. The window size is totalWords × wordLength.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859
from collections import Counter, defaultdict def find_substring(s, words): """ Find all starting indices of substrings that are concatenations of all words in 'words'. Key insight: Words all have the same length. Window size = len(words) * len(words[0]) Optimization: We can start at offsets 0, 1, ..., word_len-1 and slide by word_len each time. """ if not s or not words: return [] word_len = len(words[0]) num_words = len(words) total_len = word_len * num_words word_count = Counter(words) result = [] # Try each starting offset for offset in range(word_len): left = offset window_count = defaultdict(int) words_matched = 0 # Slide through string, word by word for right in range(offset, len(s) - word_len + 1, word_len): # Extract word at right position word = s[right:right + word_len] if word in word_count: window_count[word] += 1 words_matched += 1 # Shrink if we have too many of this word while window_count[word] > word_count[word]: left_word = s[left:left + word_len] window_count[left_word] -= 1 words_matched -= 1 left += word_len # Check if we have a valid concatenation if words_matched == num_words: result.append(left) # Shrink to continue searching left_word = s[left:left + word_len] window_count[left_word] -= 1 words_matched -= 1 left += word_len else: # Invalid word, reset window window_count.clear() words_matched = 0 left = right + word_len return resultNot every subarray or substring problem yields to sliding window. Recognizing when the technique doesn't apply is as important as recognizing when it does.
The Subarray Sum Equals K Example:
This problem illustrates a common trap. You might think: "Find subarray with sum = k, that sounds like sliding window!"
But with negatives, there's no monotonic property:
You can't decide when to shrink because shrinking might help or hurt depending on what you're removing.
Solution: Prefix Sum + Hash Map
1234567891011121314151617181920212223242526272829303132333435363738394041424344
from collections import defaultdict def subarray_sum_equals_k(nums, k): """ Count subarrays with sum exactly k. Works with negatives. This is NOT sliding window. Use prefix sums: if prefix[j] - prefix[i] = k, then subarray (i, j] has sum k. Rearranged: prefix[i] = prefix[j] - k As we compute prefix[j], count how many previous prefix sums equal prefix[j] - k. """ count = 0 prefix_sum = 0 prefix_count = defaultdict(int) prefix_count[0] = 1 # Empty prefix has sum 0 for num in nums: prefix_sum += num # How many previous prefixes give us target sum? count += prefix_count[prefix_sum - k] # Record this prefix sum prefix_count[prefix_sum] += 1 return count # Example: nums = [1, -1, 1, 1, 1, 1], k = 3# Prefix sums: [1, 0, 1, 2, 3, 4]## At prefix=1: need prefix-k=1-3=-2, count[−2]=0# At prefix=0: need -3, count[−3]=0# At prefix=1: need -2, count[−2]=0# At prefix=2: need -1, count[−1]=0# At prefix=3: need 0, count[0]=1, found 1 subarray# At prefix=4: need 1, count[1]=2, found 2 more## Total: 3 subarrays with sum 3Before applying sliding window, ask: 'If I add an element and the window becomes invalid, will removing elements from the left eventually restore validity?' If yes, and only by removal (not by luck or magic), sliding window may apply. If the answer is 'it depends on which elements,' you likely need a different approach.
Develop a systematic approach to identifying sliding window problems. Here's a checklist to run through:
| If problem asks for... | Consider... | Why |
|---|---|---|
| Max/min of k consecutive | Fixed sliding window | Size is given |
| Longest substring with constraint | Variable sliding window | Maximize size |
| Shortest substring with constraint | Variable sliding window | Minimize size |
| Subarray sum = k (positives) | Variable sliding window | Shrink when > k |
| Subarray sum = k (any integers) | Prefix sum + hash map | No monotonicity |
| Max sum subarray (any size) | Kadane's algorithm | Negatives, no constraint |
| Longest palindrome | Center expansion | Symmetry, not contiguity-based |
| Longest increasing subsequence | DP | Non-contiguous |
Trust but Verify:
Even if a problem passes the checklist, verify by considering an example:
If yes → sliding window works If "maybe, depends on what I remove" → probably doesn't work
Here's the end-to-end workflow for tackling a potential sliding window problem in an interview or practice context:
# Sliding Window Problem-Solving Workflow ## Step 1: Understand the Problem- What is the input? (array, string, etc.)- What is the constraint? (size k, at most k distinct, sum ≥ target, etc.)- What is the objective? (find max length, min length, existence, count, etc.) ## Step 2: Verify Sliding Window Applicability- □ Contiguous elements required?- □ Monotonic constraint (shrinking helps)?- □ Efficient state update possible?If all yes, proceed. Otherwise, consider alternatives. ## Step 3: Identify Window Type- Fixed size: size is given (k) → two-phase template- Variable size, maximize: "longest" → shrink when invalid- Variable size, minimize: "shortest" → shrink while valid ## Step 4: Define State- What do I track? (sum, frequency map, count, set, deque, etc.)- How do I update on entry? (add, increment, insert)- How do I update on exit? (subtract, decrement, remove) ## Step 5: Define Validity Condition- When is the window valid?- When do I shrink? (while invalid, or while valid)- When do I record result? (after shrink loop, or inside shrink loop) ## Step 6: Code the Template- Handle edge cases first (empty input, k too large, etc.)- Implement two phases (fixed) or expand-shrink (variable)- Update state correctly on both entry and exit- Record result at the right time ## Step 7: Trace Through Example- Pick a small, representative example- Trace pointer positions and state at each step- Verify result matches expected ## Step 8: Analyze Complexity- Time: O(n) or O(n log k) depending on state structure- Space: O(1) to O(k) depending on what you track- Explain amortization if askedIn interviews, verbalize your pattern recognition: 'This asks for the longest substring with a constraint on distinctness. That's a classic variable-size sliding window pattern. I'll track distinct count and shrink when it exceeds k.' This demonstrates structured thinking.
You've completed a comprehensive journey through the sliding window technique. Let's consolidate the module's key learnings:
Your Sliding Window Toolkit:
You now possess:
What's Next:
With sliding windows mastered, you have one of the most versatile array patterns in your arsenal. The next module builds on this foundation with more array patterns: prefix sums, Kadane's variations, and in-place transformations. These complement sliding window, forming a comprehensive toolkit for array problems.
Congratulations! You've mastered one of the most important algorithmic patterns for arrays and strings. Fixed windows, variable windows, maximum/minimum problems, substring containment—you're equipped to recognize and solve them all. Practice with real problems to solidify this knowledge into instinct.