Python Sliding Window Template
The sliding-window pattern walks two indices forward through a sequence, maintaining an aggregate (sum, count, set, dict) of the current window. It turns 'best subarray of length K' and 'longest subarray with property P' problems into single O(n) sweeps. This entry covers the fixed-size variant, the variable-size shrink-when-invalid variant, and the longest-substring-without-repeats classic.
1,181 views
5
def max_sum_window(nums, k):
"""Maximum sum of any contiguous subarray of length k."""
if k <= 0 or k > len(nums):
return 0
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k] # add new tail, drop old head
if window > best:
best = window
return best
print(max_sum_window([2, 1, 5, 1, 3, 2], 3)) # 9 (5 + 1 + 3)
print(max_sum_window([1, 2, 3, 4, 5], 1)) # 5 (single max)
print(max_sum_window([1, 2, 3, 4, 5], 5)) # 15 (whole array)
print(max_sum_window([5, 5, 5, 5], 2)) # 10 (all equal)
print(max_sum_window([], 3)) # 0 (empty input)
print(max_sum_window([1, 2], 5)) # 0 (k > n)For a fixed-size window the trick is to compute the first window in O(k), then slide one position at a time by adding the new right-hand element and subtracting the one that fell off the left. The running sum stays correct without re-summing K elements per step, which drops the runtime from O(n*k) to O(n). The same shape works for any aggregate that can be updated incrementally: count of true values, max via a monotonic deque, or a Counter for character frequencies. Always handle k > n and empty inputs explicitly.
def shortest_subarray_with_sum_at_least(nums, target):
"""Length of the shortest contiguous subarray whose sum >= target. 0 if none."""
n = len(nums)
left = 0
window = 0
best = n + 1
for right in range(n):
window += nums[right]
while window >= target: # shrink while the window is still valid
best = min(best, right - left + 1)
window -= nums[left]
left += 1
return 0 if best == n + 1 else best
print(shortest_subarray_with_sum_at_least([2, 3, 1, 2, 4, 3], 7)) # 2 (4 + 3)
print(shortest_subarray_with_sum_at_least([1, 1, 1, 1, 1, 1], 4)) # 4 (any 4 of them)
print(shortest_subarray_with_sum_at_least([5], 5)) # 1 (single element exact)
print(shortest_subarray_with_sum_at_least([1, 2], 100)) # 0 (impossible)
print(shortest_subarray_with_sum_at_least([], 1)) # 0 (empty input)Variable-size windows expand the right pointer one step at a time and shrink the left pointer in an inner while loop until the window is no longer valid (or no longer optimal). The amortized cost stays O(n) because each index enters the window at most once and leaves at most once. This template fits 'shortest / longest contiguous subarray that satisfies a constraint': sum, count of distinct, max minus min. The shape requires the constraint to be monotone in window size, which is why it does not work for arbitrary predicates.
def longest_unique_substring(s):
"""Length of the longest substring with no repeated character."""
last = {}
left = 0
best = 0
for right, ch in enumerate(s):
if ch in last and last[ch] >= left:
left = last[ch] + 1 # jump left past the last occurrence
last[ch] = right
if right - left + 1 > best:
best = right - left + 1
return best
print(longest_unique_substring('abcabcbb')) # 3 ('abc')
print(longest_unique_substring('bbbbb')) # 1
print(longest_unique_substring('pwwkew')) # 3 ('wke')
print(longest_unique_substring('')) # 0
print(longest_unique_substring('au')) # 2
print(longest_unique_substring('dvdf')) # 3 (jump-then-extend correctness)When the constraint is 'all characters unique', a hash map of char -> last_seen_index lets you jump the left pointer past the previous occurrence in O(1). Guarding the jump with last[ch] >= left is what makes 'dvdf' return 3 instead of 2: an old occurrence of 'd' lives outside the current window and must not pull left backwards. This pattern generalizes to 'at most K distinct characters' (replace the dict check with a len(window_counter) > k shrink loop) and 'all from a target multiset' (Minimum Window Substring). The structure is the same; only the validity test changes.