Sliding Window
Algorithms·intermediate·~40 min read
- sliding-window
- algorithm
- pattern
What you'll learn
GOLDEN RULE: When to Use Sliding Window
Use sliding window when the problem asks about a contiguous subarray or substring and you need to find an optimal result (minimum/maximum length, sum, count) under some constraint. Key signals: - "Contiguous subarray" or "substring" (NOT…
Two Variants
Sliding window comes in two flavors: | Variant | Window Size | When to Use | |---------|-------------|-------------| | Fixed-size | Constant K | "Subarray of size K", "every window of length K" | | Variable-size | Grows/shrinks | "Minimu…
Fixed-Size Window Template
When the window size K is known upfront, the pattern is straightforward: Key insight: Each slide is O(1) — you add one element and remove one element, giving O(n) total time instead of O(n k) for recomputing each window. ---
Variable-Size Window Template
When you need to find the minimum or maximum window satisfying a constraint: Key insight: Even though there's a while loop inside the for loop, each element is added at most once and removed at most once. Total operations: O(2n) = O(n).
The "Don't Reset, Contract" Principle
The fundamental optimization insight behind variable-size windows is: when the window becomes invalid, contract from the left rather than resetting entirely. Contracting preserves all the prior work you've done expanding the right side.…
Pattern 1: Maximum Sum Subarray of Size K
Problem: Given an array of integers and a number K, find the maximum sum of any contiguous subarray of size K. Approach: Fixed-size window. Maintain a running sum; slide by adding the new right element and subtracting the departing left…
Pattern 2: Smallest Subarray with Sum >= Target
Problem: Given an array of positive integers and a target sum, find the length of the smallest contiguous subarray whose sum is greater than or equal to the target. Approach: Variable-size window. Expand until the sum meets the target, t…
Pattern 3: Longest Substring with at Most K Distinct Characters
Problem: Given a string, find the length of the longest substring containing at most K distinct characters. Approach: Variable-size window with a frequency map. Expand by adding characters; shrink when distinct count exceeds K. Key insig…
Pattern 4: Longest Substring Without Repeating Characters
Problem: Find the length of the longest substring without any repeating characters.
Approach A: Set-Based
Approach B: Map-Based (Optimized)
Instead of shrinking one character at a time, jump the left pointer directly to one past the last occurrence of the duplicate character: Comparison: | Approach | Time | Space | Advantage | |----------|------|-------|-----------| | Set-ba…
Pattern 5: Character Replacement (Maximum Repeating with K Changes)
Problem: 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. Key Insight: A window is valid when windowsize - countofmostfrequentchar Importan…
Pattern 6: Minimum Window Containing All Target Characters
Problem: Given strings s and t, find the minimum window in s that contains all characters of t (including duplicates). Approach: Variable-size window with two frequency maps. Track how many required characters are "satisfied" to know whe…
Pattern 7: Sliding Window Maximum (Monotonic Deque)
Problem: Given an array and window size K, find the maximum element in every window of size K. Key Insight: Use a monotonic decreasing deque that stores indices. The front of the deque always holds the index of the maximum element in the…
Pattern 8: Fixed Window with Word-Sized Chunks
Problem: Given a string and a list of words (all same length), find all starting indices where the concatenation of all words (in any order) appears as a substring. Approach: Since all words have the same length w, treat the string as ch…
Decision Tree: Choosing the Right Variant
---
Common Pitfalls
1. Off-by-One Errors
- Window size is right - left + 1 (inclusive on both ends) - A fixed window of size K means right - left + 1 == k, so left = right - k + 1
2. Stale Entries in Hash Maps
- Always clean up entries when count reaches zero - Stale entries cause len(map) to give wrong distinct counts
3. When to Reset vs. Shrink
- Shrink: The window can potentially become valid again by removing left elements (e.g., sum constraints with positive numbers) - Reset: The window is fundamentally broken and no amount of shrinking helps (e.g., encountering an invalid c…
4. Negative Numbers
- Sliding window for sum-based problems generally requires positive numbers for the shrink logic to work. If numbers can be negative, shrinking doesn't guarantee the sum decreases, breaking the invariant. - For arrays with negatives, con…
5. Not Updating maxfreq When Shrinking (Character Replacement)
- In some problems (like character replacement), you can safely skip updating the maxfrequency when shrinking because a stale max only prevents finding larger windows. In other problems, you must maintain exact counts. ---
Complexity Summary
| Pattern | Time | Space | Key Data Structure | |---------|------|-------|--------------------| | Max sum of size K | O(n) | O(1) | Running sum | | Smallest subarray >= target | O(n) | O(1) | Running sum | | Longest with K distinct | O(n…
Final Mental Model
Think of sliding window as a caterpillar crawling along the array: 1. The right pointer (head) always moves forward, exploring new elements 2. The left pointer (tail) follows when needed, shedding elements to maintain validity 3. Between…
Practice Progression
Build your sliding window intuition in this order: 1. Fixed-size warm-up: Max sum subarray of size K (just running sum) 2. Variable-size basic: Smallest subarray with sum >= target (expand/shrink with sum) 3. Frequency map intro: Longest…
Edge Cases to Always Consider
- Empty input: Return 0 or empty string immediately - K larger than array length: Handle gracefully (return 0 or the full array) - Single element: Window of size 1 is always valid - All elements identical: Test that your distinct-charact…
Sliding Window vs. Two Pointers
While sliding window uses two pointers, not all two-pointer problems are sliding windows: | Sliding Window | General Two Pointers | |---|---| | Both pointers move in same direction | Pointers can move toward each other | | Maintains a co…