Sliding Window Pattern
Sliding Window Pattern
Sliding window is useful when you need to evaluate contiguous ranges efficiently.
When to use
- "longest/shortest subarray or substring"
- constraints that suggest O(n) over O(n^2)
Fixed window template
def fixed_window(nums, k):
window_sum = 0
best = float('-inf')
for i, x in enumerate(nums):
window_sum += x
if i >= k:
window_sum -= nums[i - k]
if i >= k - 1:
best = max(best, window_sum)
return best
Variable window template
def variable_window(s):
left = 0
seen = set()
best = 0
for right, ch in enumerate(s):
while ch in seen:
seen.remove(s[left])
left += 1
seen.add(ch)
best = max(best, right - left + 1)
return best
Practice
- Longest Substring Without Repeating Characters
- Minimum Window Substring
- Sliding Window Maximum