Sliding Window
The Intuition
You're on a train, looking through a window. As the train moves forward, the scenery shifts. A new building appears on the right edge of your view. An old one disappears off the left edge. You don't re-examine everything in the window each time. You just notice what entered and what left.
That's the whole idea. You have a range of elements, and you slide it across your data. For a fixed-size window, the count of elements inside never changes. One comes in on the right, one drops off the left. You update your running calculation (sum, count, max, whatever) by adding the new element and removing the old one. Constant work per step instead of recounting the entire window.
Variable-size windows are a little different. Imagine your window is elastic. You keep stretching the right side, pulling in more elements, as long as some condition holds (say, at most 3 distinct characters). The moment the condition breaks, you start shrinking from the left until it's valid again. The right side never moves backward. The left side never moves backward. Both march forward, and every element enters and exits the window at most once. That's why the whole thing is O(n) even though it looks like there are nested loops.
Subarray/substring problems. Maximum sum of size k, longest substring without repeating characters, minimum window containing all characters, etc.
- Non-contiguous subsets (use DP or backtracking)
- Need to compare elements far apart (use two pointers)
- Order of elements matters beyond the window (use stack)
Variations:
- Fixed-size window: Window size is constant; slide both ends together.
- Variable-size window: Expand right pointer, shrink left pointer when constraint is violated.
- With hash map: Track character frequencies or element counts within the window.
- window larger than array
- empty string
- all identical characters
Key Points
- •Maintain a window [left, right] that expands and contracts
- •Expand right to include new elements, shrink left to maintain constraints
- •Track window state with a hash map or counter
- •Fixed-size windows slide by moving both pointers together
- •Variable-size windows grow/shrink based on conditions
Code Template
1 def sliding_window_variable(s, k):
2 """Longest substring with at most k distinct characters."""
3 from collections import defaultdict
4 count = defaultdict(int)
5 left = 0
6 max_len = 0
7
8 for right in range(len(s)):
9 count[s[right]] += 1
10
11 while len(count) > k:
12 count[s[left]] -= 1
13 if count[s[left]] == 0:
14 del count[s[left]]
15 left += 1
16
17 max_len = max(max_len, right - left + 1)
18
19 return max_len
20
21 def sliding_window_fixed(arr, k):
22 """Maximum sum of subarray of size k."""
23 window_sum = sum(arr[:k])
24 max_sum = window_sum
25
26 for i in range(k, len(arr)):
27 window_sum += arr[i] - arr[i - k]
28 max_sum = max(max_sum, window_sum)
29
30 return max_sumCommon Mistakes
- Not updating window state when shrinking from the left
- Off-by-one errors when calculating window size
- Forgetting to handle the empty input case