Fixed-Size Window Problems
Fixed-size sliding window problems maintain a window of constant size k as it moves through the array.
Pattern Recognition
Fixed window problems often ask:
- "...of size k"
- "...in any k consecutive elements"
- "...every k elements"
The Template
def fixed_window_template(arr, k):
if len(arr) < k:
return handle_edge_case()
# Initialize first window
window_state = {}
for i in range(k):
update_state(window_state, arr[i])
result = process_window(window_state)
# Slide window
for i in range(k, len(arr)):
# Remove left element
remove_from_state(window_state, arr[i - k])
# Add right element
add_to_state(window_state, arr[i])
# Process current window
result = update_result(result, window_state)
return result
Problem 1: Maximum Sum Subarray of Size K
Problem: Find maximum sum of any contiguous subarray of size k.
def max_sum_subarray(nums, k):
if len(nums) < k:
return 0
# First window
window_sum = sum(nums[:k])
max_sum = window_sum
# Slide
for i in range(k, len(nums)):
window_sum = window_sum - nums[i - k] + nums[i]
max_sum = max(max_sum, window_sum)
return max_sum
nums = [2, 1, 5, 1, 3, 2]
print(max_sum_subarray(nums, 3)) # 9 (5 + 1 + 3)
Time: O(n), Space: O(1)
Problem 2: Average of Subarrays
Problem: Return array of averages for each k-sized subarray.
def find_averages(nums, k):
result = []
window_sum = 0
for i in range(len(nums)):
window_sum += nums[i]
if i >= k - 1:
result.append(window_sum / k)
window_sum -= nums[i - (k - 1)]
return result
nums = [1, 3, 2, 6, -1, 4, 1, 8, 2]
print(find_averages(nums, 5))
# [2.2, 2.8, 2.4, 3.6, 2.8]
Problem 3: Max in Each Window
Problem: Find maximum value in each sliding window of size k.
from collections import deque
def max_sliding_window(nums, k):
result = []
dq = deque() # Store indices
for i in range(len(nums)):
# Remove indices outside window
while dq and dq[0] <= i - k:
dq.popleft()
# Remove smaller elements (not useful)
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
dq.append(i)
# Add to result once we have k elements
if i >= k - 1:
result.append(nums[dq[0]])
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(max_sliding_window(nums, 3))
# [3, 3, 5, 5, 6, 7]
Key: Use monotonic deque to track maximum efficiently.
Problem 4: First Negative in Each Window
Problem: Find first negative number in each window of size k.
from collections import deque
def first_negative_in_window(nums, k):
result = []
negatives = deque() # Store indices of negatives
for i in range(len(nums)):
# Add if negative
if nums[i] < 0:
negatives.append(i)
# Remove indices outside window
while negatives and negatives[0] <= i - k:
negatives.popleft()
# Add result once window is formed
if i >= k - 1:
if negatives:
result.append(nums[negatives[0]])
else:
result.append(0)
return result
nums = [12, -1, -7, 8, -15, 30, 16, 28]
print(first_negative_in_window(nums, 3))
# [-1, -1, -7, -15, -15, 0]
Problem 5: Contains Nearby Duplicate
Problem: Check if array has duplicates within k distance.
def contains_nearby_duplicate(nums, k):
window = set()
for i in range(len(nums)):
# Check if in window
if nums[i] in window:
return True
# Add to window
window.add(nums[i])
# Remove if window too large
if len(window) > k:
window.remove(nums[i - k])
return False
print(contains_nearby_duplicate([1,2,3,1], 3)) # True
print(contains_nearby_duplicate([1,0,1,1], 1)) # True
print(contains_nearby_duplicate([1,2,3,1,2,3], 2)) # False
Problem 6: K Distinct Characters
Problem: Check if window of size k has all distinct characters.
def all_distinct_in_window(s, k):
"""Return True if any window of size k has all distinct chars"""
if k > len(s):
return False
freq = {}
distinct = 0
for i in range(len(s)):
# Add right char
char = s[i]
freq[char] = freq.get(char, 0) + 1
if freq[char] == 1:
distinct += 1
# Remove left char if window too large
if i >= k:
left_char = s[i - k]
freq[left_char] -= 1
if freq[left_char] == 0:
distinct -= 1
# Check if window of size k is all distinct
if i >= k - 1 and distinct == k:
return True
return False
print(all_distinct_in_window("abcdefg", 3)) # True
print(all_distinct_in_window("aabbc", 3)) # False
Problem 7: Maximum of All Subarrays
Problem: Product of max and min in each window of size k.
from collections import deque
def max_min_product(nums, k):
max_dq = deque() # Decreasing
min_dq = deque() # Increasing
result = []
for i in range(len(nums)):
# Maintain decreasing deque for max
while max_dq and nums[max_dq[-1]] <= nums[i]:
max_dq.pop()
max_dq.append(i)
# Maintain increasing deque for min
while min_dq and nums[min_dq[-1]] >= nums[i]:
min_dq.pop()
min_dq.append(i)
# Remove out of window
while max_dq and max_dq[0] <= i - k:
max_dq.popleft()
while min_dq and min_dq[0] <= i - k:
min_dq.popleft()
# Calculate once window formed
if i >= k - 1:
max_val = nums[max_dq[0]]
min_val = nums[min_dq[0]]
result.append(max_val * min_val)
return result
nums = [1, 3, 2, 5, 4]
print(max_min_product(nums, 3))
# [6, 15, 20] (3*2, 5*3, 5*4)
Tips for Fixed Window
- Initialize first window carefully: Make sure indices are correct
- Use the formula:
window_end - window_start + 1 == k - Consider deques: For min/max tracking
- Update efficiently: Remove one, add one per iteration
- Edge cases: k > n, k = 1, empty array