Sliding Window

Fixed-size sliding window computes running aggregates in O(n). Core optimization pattern.

mx = cur = sum(a[:k])
for i in range(k, len(a)):
    cur += a[i] - a[i-k]
    mx = max(mx, cur)

Single-pass tracking of running minimum and maximum profit. Classic greedy O(n) solution.

mn = float('inf')
mx = 0
for p in prices:
    mn = min(mn, p)
    mx = max(mx, p - mn)

The generic expand-right / shrink-left template handles all variable-length window problems.

l = 0
for r in range(len(s)):
    # add s[r]
    while invalid():
        # remove s[l]
        l += 1

Hash-map window tracks last index of each char. Avoids set removal on duplicates.

seen = {}
l = res = 0
for r, c in enumerate(s):
    if c in seen and seen[c] >= l:
        l = seen[c] + 1
    seen[c] = r
    res = max(res, r - l + 1)

Counter-based fixed window slides character frequencies. Powers anagram detection.

from collections import Counter
w = Counter(s[:k])
for i in range(k, len(s)):
    w[s[i]] += 1
    w[s[i-k]] -= 1
    if w[s[i-k]] == 0: del w[s[i-k]]

Tracking have/need counts is the matching logic inside minimum-window-substring.

need, have = len(cnt_t), 0
for c in window:
    window_cnt[c] += 1
    if window_cnt[c] == cnt_t[c]:
        have += 1

Monotonic deque keeps the running maximum in O(1) per step. Key for window-maximum.

from collections import deque
d = deque()
for i, x in enumerate(a):
    while d and a[d[-1]] <= x: d.pop()
    d.append(i)
    if d[0] <= i - k: d.popleft()

Fixed window: add right, remove left when size > k. Variable window: expand right, shrink left until valid.

FIXED vs VARIABLE SIZE SLIDING WINDOW
──────────────────────────────────────
FIXED SIZE (window = k):
  for i in range(len(a)):
      # add a[i] to window
      if i >= k:
          # remove a[i-k] from window
      if i >= k - 1:
          # window is full, record answer
  Examples: max sum of k consecutive, moving average

VARIABLE SIZE (expand/shrink):
  l = 0
  for r in range(len(a)):
      # expand: add a[r]
      while window_invalid():
          # shrink: remove a[l]
          l += 1
      # update answer with window [l..r]
  Examples: longest substring without repeats,
            minimum window substring

DECISION:
  "Exactly k elements"    → fixed window
  "At most k distinct"    → variable, shrink when > k
  "Minimum window with X" → variable, shrink when valid
  "Maximum window with Y" → variable, shrink when invalid

Prefix sum handles arbitrary ranges and negatives. Sliding window needs monotonic behavior but uses O(1) space.

PREFIX SUM vs SLIDING WINDOW
─────────────────────────────
PREFIX SUM:
  pre = [0] * (n + 1)
  for i in range(n): pre[i+1] = pre[i] + a[i]
  sum(a[l:r]) = pre[r] - pre[l]   # O(1) range sum

  Use when:
  □ Multiple range sum queries
  □ Subarray sum equals k (hash + prefix sum)
  □ Non-contiguous or arbitrary ranges
  □ 2D range sums

SLIDING WINDOW:
  Maintain running sum, add right, remove left

  Use when:
  □ Contiguous subarray of fixed/variable size
  □ "Longest/shortest subarray with property X"
  □ All elements positive (monotonic window behavior)

KEY DIFFERENCE:
  Prefix sum: any range query, even with negatives
  Sliding window: contiguous + positive/monotonic only

  "Subarray sum = k" with negatives → prefix sum + hashmap
  "Subarray sum = k" all positive   → sliding window
  "Max sum of size k"               → sliding window

Window is valid when (window_size - max_freq) <= k. max_freq only needs to increase — shrinking the window can't help.

count = {}
l = max_freq = 0
for r in range(len(s)):
    count[s[r]] = count.get(s[r], 0) + 1
    max_freq = max(max_freq, count[s[r]])
    if (r - l + 1) - max_freq > k:
        count[s[l]] -= 1
        l += 1