Maintain a window of elements and slide it across the array to find optimal subarrays
The sliding window pattern maintains a contiguous subset of elements (window) and efficiently slides it across the array. It can be fixed-size or variable-size, and often uses a hash map to track element frequencies within the window.
Use when finding subarrays or substrings with specific properties, such as maximum/minimum sum, longest substring with k distinct characters, or finding all anagrams. Particularly useful when the problem asks for contiguous elements.
Fixed vs variable window: expand to include new elements, then shrink while invariant is broken; keep O(1) updates for fast slides.
def sliding_window(s, k):
window_start = 0
max_length = 0
char_frequency = {}
for window_end in range(len(s)):
# Expand window
right_char = s[window_end]
char_frequency[right_char] = char_frequency.get(right_char, 0) + 1
# Shrink window if needed
while len(char_frequency) > k:
left_char = s[window_start]
char_frequency[left_char] -= 1
if char_frequency[left_char] == 0:
del char_frequency[left_char]
window_start += 1
# Update result
max_length = max(max_length, window_end - window_start + 1)
return max_lengthWindow size remains constant as it slides across the array
def fixed_window(arr, k):
if len(arr) < k:
return 0
# Calculate first window
window_sum = sum(arr[:k])
max_sum = window_sum
# Slide window
for i in range(k, len(arr)):
window_sum = window_sum - arr[i - k] + arr[i]
max_sum = max(max_sum, window_sum)
return max_sumFixed window maintains size k; variable window expands then shrinks while the invariant is violated
def fixed_max_sum(arr, k):
if len(arr)<k: return 0
s=sum(arr[:k]); best=s
for i in range(k,len(arr)):
s+=arr[i]-arr[i-k]
best=max(best,s)
return best
def longest_k_distinct(s, k):
from collections import defaultdict
cnt=defaultdict(int); l=0; best=0
for r,ch in enumerate(s):
cnt[ch]+=1
while len(cnt)>k:
cnt[s[l]]-=1
if cnt[s[l]]==0: del cnt[s[l]]
l+=1
best=max(best, r-l+1)
return bestWindow size changes dynamically based on conditions
def variable_window(s, k):
window_start = 0
max_length = 0
char_freq = {}
for window_end in range(len(s)):
# Expand window
right_char = s[window_end]
char_freq[right_char] = char_freq.get(right_char, 0) + 1
# Shrink window if needed
while len(char_freq) > k:
left_char = s[window_start]
char_freq[left_char] -= 1
if char_freq[left_char] == 0:
del char_freq[left_char]
window_start += 1
# Update result
max_length = max(max_length, window_end - window_start + 1)
return max_lengthCombines sliding window with hash map for character/element tracking
def window_with_freq(s, pattern):
pattern_freq = {}
for char in pattern:
pattern_freq[char] = pattern_freq.get(char, 0) + 1
window_start = 0
matched = 0
result = []
for window_end in range(len(s)):
right_char = s[window_end]
if right_char in pattern_freq:
pattern_freq[right_char] -= 1
if pattern_freq[right_char] == 0:
matched += 1
if matched == len(pattern_freq):
result.append(window_start)
if window_end >= len(pattern) - 1:
left_char = s[window_start]
if left_char in pattern_freq:
if pattern_freq[left_char] == 0:
matched -= 1
pattern_freq[left_char] += 1
window_start += 1
return resultMaintain a decreasing deque of indices for O(1) max per slide
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # indices, decreasing by value
res = []
for i, v in enumerate(nums):
while dq and dq[0] <= i - k:
dq.popleft()
while dq and nums[dq[-1]] <= v:
dq.pop()
dq.append(i)
if i >= k - 1:
res.append(nums[dq[0]])
return resEach element is visited at most twice (once when expanding, once when shrinking).
Space depends on window size or number of distinct elements tracked (typically O(k) or O(1)).