Sliding window: keep a chunk, slide the edges

Picture a moving chunk of an array or string.
You advance the right edge, sometimes the left, and track state inside the chunk. You never re-read what you already processed.

Jon Postel put the idea in RFC 793 (1981) as TCP flow control.
RFC 7323 adds window scaling. Wikipedia keeps a separate sliding window protocol page. The interview shape is the same trick on one array.

“Name the invariant and the state. One sentence each, before you type.”

Bentley’s Programming Pearls Column 8 packed related linear-array thinking for a generation, including Kadane’s maximum subarray story.
Jeff Erickson’s open Algorithms is where I send people for the amortized “each index enters and leaves once” argument.

What you are maintaining

You can compute the answer for [left, right+1) from [left, right) with a constant-time update.
State is whatever bookkeeping keeps that invariant true.

Before coding, say three things: the state, the invariant, the rule that moves the edges.

When to reach for it

• Contiguous subarray or substring
• Max/min of k consecutive elements → fixed window
• Longest/shortest under a constraint → variable window
• At most K distinct / without repeating → variable + frequency map
• “In the last N requests” → production rate-limit shape

Non-contiguous / any subset → different family (DP or search). Stop.

Fixed vs variable

Fixed

Width k is given. Slide and update the aggregate. O(n), not O(n·k).

# Fixed window: max sum of k consecutive elements
def max_sum_subarray(nums, k):
  window_sum = sum(nums[:k])
  max_sum = window_sum
  for i in range(k, len(nums)):
      window_sum += nums[i] - nums[i - k]
      max_sum = max(max_sum, window_sum)
  return max_sum

Variable

Expand on the right. Shrink on the left while the invariant is broken.
Use while, not if — one expansion can break the invariant by more than one element.

Sedgewick’s Princeton Algorithms treats the frequency-map window as a standard hash-table application.

# Variable window: longest substring with at most K distinct chars
def longest_k_distinct(s, k):
  counts, left, best = {}, 0, 0
  for right in range(len(s)):
      counts[s[right]] = counts.get(s[right], 0) + 1
      while len(counts) > k:
          counts[s[left]] -= 1
          if counts[s[left]] == 0: del counts[s[left]]
          left += 1
      best = max(best, right - left + 1)
  return best

The template

Expand, shrink, update: those three steps are the whole loop. If you catch yourself in nested loops re-summing the window, you left the template.

Walk abcabcbb for Longest Substring Without Repeating Characters: right moves, a repeat lands, left shrinks until the invariant holds, then update best.

Problems worth drilling

Subpatterns

Sum windows. Fine for fixed width, or variable with non-negatives. Negatives can make shrink grow the sum — stop and switch technique.

Frequency windows. Map counts in the current window, not the whole string. Ask yourself which window the map describes.

Deque windows. For max or min of the live window, keep a monotonic deque. Erickson’s stack/queue chapters are the clean read.

Why it is O(n)

The inner while looks nested. Each index enters at most once and leaves at most once. Total moves ≤ 2n — amortized linear (Erickson, maximum subarray history).

• Time: O(n)
• Space: O(k) / O(alphabet) / O(1) depending on state

Mistakes I still see

• Off-by-one on right - left + 1
• Forgetting to delete a key when its count hits zero
• Calling it sliding window when the selection can have gaps

Where it ships

TCP. Sequence windows in RFC 793 / RFC 7323.

Rate limiters. Fixed per-minute buckets allow a 2× burst across a minute boundary. Sliding windows kill that artifact — see Stripe’s rate limiters, Cloudflare’s counting post, .NET SlidingWindowRateLimiter, Redis rate limiting.

Same expand / shrink / update idea, just at production scale.

Practice order

1. Max sum of size k (fixed warm-up above)
2. Best Time to Buy and Sell Stock
3. Longest Substring Without Repeating Characters
4. Minimum Window Substring
5. Longest Repeating Character Replacement
6. Permutation in String
7. Sliding Window Maximum
8. Subarray Sum Equals K — deliberately not window; catch the misread

Say the invariant out loud on each. Then write.

Further reading

• RFC 793, RFC 7323
• Erickson, Algorithms
• Sedgewick, algs4 hash tables
• Sliding window protocol, Maximum subarray