Sliding Window
DSA · Arrays and Searching
Theory
A sliding window keeps a contiguous range of elements and moves it across the array, adding the element that enters on the right and removing the one that leaves on the left. Instead of recomputing each window from scratch, it updates a running value, so the total work is O(n). Windows can have a fixed size (average of every k days) or a variable size that grows and shrinks to satisfy a condition.
Why we use it
It turns repeated work over overlapping ranges into a single linear pass.
When to use it
Use it for subarray or substring problems: maximum sum of k items, longest substring without repeats, smallest window meeting a total, moving averages.
How it works
- Start: left = 0, window empty
- For right = 0..n-1: add arr[right] to window
- Window breaks the rule (too big / invalid)? Yes: Remove arr[left], left = left + 1, check again. No: Update best answer.
- Return best answer after the last right
Syntax
Fixed window of size k:
window = sum(arr[:k])
for i in range(k, n):
window += arr[i] - arr[i-k]
Variable window:
for right in range(n):
add arr[right]
while window invalid: remove arr[left]; left += 1Example
def max_sum_k(nums, k):
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k]
best = max(best, window)
return best
def longest_unique(s):
seen = {}
left = best = 0
for right, ch in enumerate(s):
if ch in seen and seen[ch] >= left:
left = seen[ch] + 1
seen[ch] = right
best = max(best, right - left + 1)
return best
print("Best 3-day sales:", max_sum_k([120, 80, 150, 90, 200, 60], 3))
print("Longest unique substring:", longest_unique("abcabcbb"))Key points
- Window must be contiguous
- Update the window instead of recomputing it
- Fixed and variable window variants
- O(n) time for most window problems