Sliding Window Algorithm — the pattern I learned the hard way

A sliding window is a moving chunk of an array or string that you slide one step at a time. You advance the right edge, sometimes move the left edge, and track whatever matters inside the chunk. The win: you never re-read what you already read.

Sliding window is not a LeetCode pattern Google invented in 2015. Jon Postel standardized it in RFC 793 in September 1981 as the core flow-control mechanism for TCP. Every HTTP request loading this page moved across a sliding window of sequence numbers. The algorithmic pattern you will see in an interview is the same mental model shrunk to a single array: maintain a bounded chunk of state, advance one end at a time, never recompute what you already know.

The name is canonical enough that Wikipedia has a dedicated Sliding window protocol page distinct from any algorithm textbook entry. RFC 7323 extends the original 1981 design with window scaling so the idea holds up on multi-gigabit links. The production shape and the interview shape are literally the same trick.

“Name the invariant and name the state. One sentence each, before you touch the keyboard. If you cannot, you do not understand the problem yet — keep reading it.”

The interview version is a family of contiguous-subarray and substring problems where brute force is O(n^2) or O(n*k) and sliding window compresses it to O(n). The technique was popularized for algorithmic work by Jon Bentley's Programming Pearls Column 8 (1984) — the same column that packaged Joseph Kadane's maximum subarray algorithm for a generation of engineers. This post classifies the interview shapes, walks the canonical problems with references to open course material, and hands you off to the textbooks, RFCs, and production systems that go deeper.

What the pattern actually is

Sliding window is the pattern for contiguous subarrays and substrings where the answer for window [left, right+1) can be computed from the answer for window [left, right) plus a constant-time update, rather than recomputed from scratch. The state is whatever bookkeeping you need to preserve an invariant as the window slides.

Jeff Erickson's open-source Algorithms textbook frames linear-time array work through amortized analysis: each array element enters the window at most once and leaves at most once, so even with a nested-looking inner loop the total work is O(n). That is the line you want to be able to recite cold when an interviewer asks "why is this linear, not quadratic?"

The real question is not "can you use two pointers?" It is: can you name the state, name the invariant, and name the rule that moves the boundaries? Three sentences. Strong candidates say them before coding. Weak candidates start typing and hope structure emerges.

Recognition signals

Start thinking sliding window when the prompt contains:

• "Contiguous subarray" or "substring" — the window must be contiguous, or the pattern does not apply
• "Maximum / minimum sum of k elements" — fixed window
• "Longest / shortest" with a constraint — variable window
• "At most K distinct" or "without repeating" — variable window with a frequency map
• "In the last N requests / seconds" — this is the production shape (rate limiter)

"Non-contiguous" or "any subset" immediately knocks the pattern out — that is a backtracking or DP problem. Navdeep Singh's NeetCode roadmap keeps Sliding Window as a dedicated lane because the family repeats constantly in callback rounds at Google, Meta, Amazon, and Microsoft.

The two interview shapes

There are only two shapes that matter: fixed and variable. Fixed gives you a known width k. Variable gives you an invariant to defend and a stopping condition for the shrink.

Fixed window

Fixed is the easy case. You are given k. You slide a k-wide window across the array and update the running aggregate on each move instead of re-computing from scratch. Total work is O(n) instead of O(n*k). That is the whole trick.

# 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 window

Variable is where most candidates leak points. The window expands when a new element arrives on the right and shrinks when an invariant breaks on the left. The common bug is using if instead of while on the shrink step — one expansion can violate the invariant by more than one element, and a single-step shrink does not fully restore it.

Robert Sedgewick's Princeton Algorithms, 4th Edition treats the frequency-map-backed variable window as a standard application of hash tables. The interviewing.io walkthrough for "longest substring with at most K distinct characters" is the canonical public interview transcript for this shape — it is worth watching once to see how a strong candidate narrates the invariant out loud.

# 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

Every variable-window problem fits one three-line template. Fill in state and invariant and you are done:

Expand. Shrink. Update. The rest is bookkeeping. If you catch yourself writing nested loops or recomputing a sum over the window, you have drifted off the template — go back to the three comments and ask which step you skipped.

That abcabcbb walkthrough is exactly what the interviewer wants to hear you narrate on "Longest Substring Without Repeating Characters." Right pointer moves. Repeat arrives. Left pointer shrinks until the invariant is true again. Best length updates only on valid windows. The NeetCode problem page at neetcode.io/problems/longest-substring-without-duplicates mirrors the same walkthrough with video explanation from Singh.

The canonical interview questions

These are the questions interviewers recycle. Every major public prep platform tracks the same list because the variations compose — solve the first five and you can usually derive the rest in the room.

Subpatterns worth naming

Sum-based windows. Track a running sum for fixed windows, or for variable windows where all values are non-negative. One trap: the moment the array contains negatives, shrinking can make the sum grow instead of shrink, and the monotonic "expand until too big, shrink until valid" logic silently breaks. For Subarray Sum Equals K on NeetCode, do not reach for sliding window — use prefix sum plus a hash map. Pattern-matching the wrong technique here is the failure mode interviewers flag.

Frequency-based windows. Track counts with a map. This is the default for anagram problems, distinct-count problems, and minimum-window questions. The common bug is forgetting what the frequency map represents: counts in the current window, not counts in the full input. Candidates who cannot answer "which window does this map describe?" are one step from a wrong answer.

Deque-based windows. Used when the question asks for the max or min of the current window, not just a sum or validity check. The data structure is a monotonic deque, and "Sliding Window Maximum" is the canonical form. Erickson's Chapter 2 on stacks and queues is the cleanest place to read up on why a deque works here and an ordinary queue doesn't.

Why the time complexity is O(n), not O(n^2)

The inner while loop looks nested, but each element enters the window at most once and is removed at most once. Total boundary moves across the whole run are 2n. This is the amortized argument — and it is the line interviewers expect to hear when they ask "what's the complexity?" Erickson's textbook works the same argument for dynamic-array doubling and treap operations; the Maximum subarray problem Wikipedia entry gives a cleaner historical source for Bentley's popularization of the technique.

• Time: O(n) — each element enters and leaves the window once
• Space: O(k) for a fixed window tracking the k elements, O(alphabet size) for a frequency-map variable window, O(1) for a sum-only window

Common mistakes

This is the single most common failure in variable-window rounds. The interviewing.io walkthrough linked above narrates exactly this bug from a real candidate tape.

A working template still fails the assertion if the recorded size is wrong by one. Write the size expression on paper first, test it against a three-element example, then plug it into the code.

The word "contiguous" is the hinge. If the problem allows gaps in the selection, the sliding window invariant does not apply — the bookkeeping cannot stay constant-time per step.

A clean guard at the top of the function costs two lines and saves the candidate from debugging a negative slice under interview pressure.

Where sliding window actually ships in production

The interview shape is the small sibling of the production shape. Three places engineers hit sliding window every day:

1. TCP flow control (1981 → today). Jon Postel's RFC 793 defined the sending side's window as a bounded range of in-flight bytes the receiver has authorized. The receive window slides forward as acknowledgments arrive. RFC 7323 added window scaling so the same protocol works on modern multi-gigabit links. Wikipedia's Sliding window protocol article traces the full lineage.

2. API rate limiters. Paul Tarjan's Scaling your API with rate limiters (Stripe engineering, 2017) walks four algorithms including a sliding window counter and a sliding window log. Microsoft ships a SlidingWindowRateLimiter in .NET that is directly the production version of the data structure interviewers ask you to prototype. Redis documents the same pattern for distributed enforcement. Envoy's local rate limit filter uses a token bucket but Envoy's distributed rate limiter uses sliding-window counters for the same reasons Stripe does.

The production bug that motivates sliding over fixed buckets: with a fixed per-minute counter, clients can send a full minute's quota in the last second of minute N and another full minute's quota in the first second of minute N+1 — an observed 2x burst on a 1x limit. Sliding window eliminates the boundary artifact. This is the same bug Julien Desgats describes in Counting things, a lot of different things on the Cloudflare engineering blog.

3. Streaming aggregations. "Count requests in the last 60 seconds," "average latency over the last 100 events," "detect a burst within a 5-minute window" — every observability and anomaly-detection system runs some form of windowed aggregation. The same expand-shrink-update template you write for a LeetCode problem is the template a production metrics pipeline uses, scaled up and distributed.

How to communicate this in an interview

The opening sentence interviewers want to hear on a sliding window problem:

"This is a contiguous-subarray problem with a constraint, so I'll use a sliding window. I'll expand right, shrink left when the invariant breaks, and track [sum / frequency map / deque] as my window state."

Then name the invariant in one sentence. This is the part most candidates skip.

• "At every step, the window contains at most k distinct characters."
• "At every step, the deque is monotonically decreasing from front to back."
• "At every step, window_sum matches the sum of the current k elements."

Three sentences. State, invariant, update rule. If you can say them, the code writes itself; if you cannot, do not start typing.

Practice roadmap

Easy

1. Maximum Sum Subarray of Size K — Fixed window, sum tracking, the warm-up (see code above)
2. Best Time to Buy and Sell Stock — NeetCode — degenerate variable window, tracks a running min

Medium

3. Longest Substring Without Repeating Characters — NeetCode — variable window, frequency map
4. Minimum Window Substring — NeetCode — variable window, frequency map plus match-count tracking. This is the question to time yourself on under 25 minutes for Meta and Google dry-runs.
5. Longest Repeating Character Replacement — NeetCode — variable window, max-frequency trick
6. Permutation in String — NeetCode — fixed window, frequency comparison

Hard

7. Sliding Window Maximum — NeetCode — fixed window plus monotonic deque
8. Subarray Sum Equals K — NeetCode — not sliding window (prefix sum + hash map) — practice identifying when the pattern does not apply

Quick reference

Go deeper

• RFC 793 — Transmission Control Protocol (Postel, 1981). The grandparent document. Section 3.4 covers window management. Required reading once in a career.
• RFC 7323 — TCP Extensions for High Performance (Borman, Braden, Jacobson, Scheffenegger, 2014). Window scaling and timestamps.
• Jeff Erickson — Algorithms (UIUC, free PDF). Chapter 2 covers stacks, queues, and amortized analysis — the foundations behind why sliding window is linear.
• Robert Sedgewick — Algorithms, 4th Edition (Princeton, with Kevin Wayne). Chapter 3.4 on hash tables is the canonical reference for the frequency-map shape.
• Jon Bentley — Programming Pearls (Bell Labs, 1986). Column 8 packaged Kadane's maximum-subarray algorithm and the contiguous-range technique for a generation of working engineers.
• Wikipedia — Maximum subarray problem. Historical context for Kadane and the family of sub-array problems sliding window solves.
• Paul Tarjan — Scaling your API with rate limiters (Stripe engineering, 2017). The clearest public writeup of the four rate-limiter flavors, including sliding window counter vs log.
• Julien Desgats — Counting things, a lot of different things (Cloudflare engineering). Distributed sliding-window counting at scale.
• Microsoft — SlidingWindowRateLimiter reference. Production .NET implementation you can read the source of.
• Navdeep Singh — NeetCode roadmap. Sliding window lane with video walkthroughs for each canonical problem.
• interviewing.io — Longest substring with at most K distinct characters. Public interview transcript of a candidate narrating the invariant.

Related patterns

“Sliding window is one move inside a small family. Two pointers is the move when both ends advance independently. Prefix sum is the move when you need arbitrary-range sums without scanning. Know which is which and the 90 percent of array problems collapse.”

• Sliding Window vs Two Pointers — same two-variable bookkeeping, different movement rules. Sliding window is a specialization of two pointers.
• Prefix Sum Pattern — the right tool when sliding window breaks (negatives, arbitrary ranges).
• Dynamic Programming Patterns — when the answer cannot be maintained in constant bookkeeping per step.

Next up: Sliding Window vs Two Pointers — related, but not the same thing.