Sliding Window — How the Pattern Works
The Sliding Window pattern maintains a contiguous range [left, right] over an array or string alongside an incremental aggregate state—such as a running sum or product, character frequency map, sliding hash set, or monotonic deque. Instead of recomputing aggregate properties from scratch across overlapping ranges, expanding right incorporates one incoming element and advancing left evicts one outgoing element in O(1) amortized time. Because both left and right advance monotonically without retreating, every index enters and leaves the window at most once, collapsing O(n * k) or O(n^2) brute-force range scans into O(n) time.
- Contiguous subarray or substring problems asking for the maximum/minimum length, optimal aggregate (sum, average, product), or count of valid contiguous runs.
- Fixed-width window queries of a specified size
k(e.g., rolling sums/averages, fixed-length substring deduplication, permutation/anagram matching, or nearby duplicates within distancek). - Dynamic-width monotonic constraints where adding elements on the right monotonically pushes a metric toward violation and removing elements on the left restores validity (e.g., positive-number sum/product caps, at most
kdistinct elements, or at mostkflips/replacements). - Exact-cardinality or 'at least' subarray counting problems reducible via
exact(k) = at_most(k) - at_most(k - 1)or complement prefix counting (total += leftafter shrinking to the boundary of invalidity).
- Using dynamic sum/score shrinking when the array contains negative numbers: evicting a negative value increases the window sum, breaking the monotonicity required by two-pointer shrinking.
- Initializing
best = 0when maximizing window sums or averages over potentially negative inputs; always seedbestwith the first valid window's aggregate or-math.inf. - Allowing
leftto move backward on stale index-map lookups (left = last[ch] + 1without checkinglast[ch] >= left), or forgettingdel count[x]whencount[x] == 0while relying onlen(count). - Attempting to count exact-sum or exact-distinct subarrays with a single window when zeros or duplicate elements exist, instead of decomposing via
at_most(k) - at_most(k - 1)(withat_most(< 0) = 0).
def fixed_window_max_sum(nums, k):
window_sum = sum(nums[:k])
best = window_sum
for right in range(k, len(nums)):
window_sum += nums[right] - nums[right - k]
best = max(best, window_sum)
return bestdef dynamic_window_longest(nums, k):
count = {}
left = best = 0
for right, val in enumerate(nums):
count[val] = count.get(val, 0) + 1
while len(count) > k:
count[nums[left]] -= 1
if count[nums[left]] == 0:
del count[nums[left]]
left += 1
best = max(best, right - left + 1)
return bestfrom collections import deque
def sliding_window_max(nums, k):
dq, result = deque(), []
for right, val in enumerate(nums):
while dq and nums[dq[-1]] <= val:
dq.pop()
dq.append(right)
if dq[0] <= right - k:
dq.popleft()
if right >= k - 1:
result.append(nums[dq[0]])
return result