Sliding Window

Fixed window slides at constant size. Variable window expands/shrinks to find optimal. Prefix sum handles arbitrary subarray queries.

SLIDING WINDOW — DECISION GUIDE
─────────────────────────────────
FIXED WINDOW (size k known):
  # init window [0..k-1]
  window_sum = sum(a[:k])
  for i in range(k, n):
      window_sum += a[i] - a[i-k]  # slide
  → Max avg subarray, string permutation check

VARIABLE WINDOW (find optimal size):
  left = 0
  for right in range(n):
      # expand: add a[right] to window state
      while window_invalid():
          # shrink: remove a[left] from window state
          left += 1
      # update answer with current window
  → Longest substring without repeats, min window substring

PREFIX SUM (need subarray sums):
  pre = [0] * (n + 1)
  for i in range(n):
      pre[i+1] = pre[i] + a[i]
  # sum(a[l..r]) = pre[r+1] - pre[l]
  → Subarray sum equals K, range sum queries

DECISION:
  Window size given?          → fixed window
  Find min/max window size?   → variable window
  Need sum of any subarray?   → prefix sum
  Need count of subarrays?    → prefix sum + hash map