Back to Topics
Sliding Window
Maintain a dynamic window (subset of elements) to optimize problems looking for contiguous subsegments.
1. Fixed Size Sliding Window
Practice Scenarios
Pseudocode Implementation
window_sum = sum of first k elements
ans = window_sum
for i from k to n:
window_sum += arr[i] - arr[i - k]
ans = max(ans, window_sum)
2. Variable Size Window (Grow + Shrink)
Practice Scenarios
Pseudocode Implementation
left = 0
for right in range(n):
add arr[right] to window
while window is invalid:
remove arr[left] from window
left += 1
update answer with valid window size (right - left + 1)
3. Minimum / Valid Window Problems
Practice Scenarios
Pseudocode Implementation
left = 0
ans = infinity
for right in range(n):
add arr[right] to window
while window meets condition:
ans = min(ans, right - left + 1)
remove arr[left] from window
left += 1
4. At Most K / Exactly K Pattern
Practice Scenarios
Pseudocode Implementation
function atMost(k):
left = 0, count = 0
for right in range(n):
add arr[right] to window
while window constraint > k:
remove arr[left]
left += 1
count += (right - left + 1)
return count
return atMost(K) - atMost(K - 1) // For exactly K
5. Frequency Constraint Windows
Practice Scenarios
Pseudocode Implementation
left = 0
freq_map = {}
for right in range(n):
freq_map[arr[right]]++
while len(freq_map) > k:
freq_map[arr[left]]--
if freq_map[arr[left]] == 0:
del freq_map[arr[left]]
left += 1
ans = max(ans, right - left + 1)
6. Monotonic Deque (Advanced)
Practice Scenarios
Pseudocode Implementation
deque = []
for i in range(n):
while deque and deque.front() < i - k:
deque.pop_front()
while deque and nums[deque.back()] < nums[i]:
deque.pop_back()
deque.push_back(i)
if i >= k - 1:
ans.append(nums[deque.front()])
7. Counting Subarrays (r - l + 1 Trick)
Practice Scenarios
Pseudocode Implementation
left = 0
ans = 0
for right in range(n):
update state with arr[right]
while state is invalid:
remove arr[left]
left += 1
ans += current_valid_combinations(right, left)
8. Hard Sliding Window Problems
Practice Scenarios
Pseudocode Implementation
// Often requires two pointers with multiple passes or complex nested state tracking
for attempt in range(variations):
left = 0
state = reset()
for right in range(n):
// complex window logic