Lesson 3 of 8 · 48 min

Sliding window

Fixed and variable sliding windows, the at-most-K template, minimum window covering, amortized O(n) reasoning, and production metaphors for rolling metrics.

Contiguous + constraint = window, not DP first

When the problem says subarray or substring (contiguous) with a constraint on the contents — at most K distinct, sum ≤ S, all unique chars, cover all of t — your first pattern candidate is sliding window, not full DP. Builders who jump to DP on every “optimal subarray” lose twenty minutes. Window = maintain a valid segment [L, R) while R scans right and L only moves right (amortized O(n)). Production metaphors: rolling 60s latency, rate-limit window, longest valid session segment.
Two shapes. Fixed window of size K: one sum/ product/ match count; slide by adding A[R] and removing A[R−K]. Variable window: grow R freely; while invalid, advance L until valid again; track best length/sum/start. The art is the validity predicate and the structure that updates it in O(1) or O(σ) (often a frequency map).
Amortized linearity: L and R each move at most n times ⇒ O(n) total if each move is O(1) or O(alphabet). If you binary search L for every R, you often still work but signal weaker pattern fluency. Prefer the two-pointer window when the predicate is monotonic: once invalid, further growth stays invalid until L advances.

Fixed window: max sum of size K

Classic warm-up. Compute sum of first K; slide: sum += a[i] − a[i−K]; track max. Edge cases: K > n, K == 0, negatives (max sum still fine). Production: max requests in any K-minute bucket if you already have per-minute counts — same math.
python
1FIXED WINDOW — max sum of size k23def max_sum_k(a: list[int], k: int) -> int:4    if k <= 0 or k > len(a):5        raise ValueError("bad k")6    s = sum(a[:k])7    best = s8    for i in range(k, len(a)):9        s += a[i] - a[i - k]10        best = max(best, s)11    return best1213# O(n) time, O(1) space. Narrate edges: k==n → whole array once.

Variable window: longest substring without repeating chars

Maintain last-seen index or a set/freq of chars in [L, R]. Expand R; if s[R] already in window, advance L past the previous occurrence. Best length = max(R−L+1). Common bug: moving L only by 1 in a loop vs jumping L to last[s[R]]+1 — both OK if freq map kept consistent; jump must still remove intervening counts if you use freq.
python
1VARIABLE WINDOW — longest substring without repeating characters23def length_of_longest_substring(s: str) -> int:4    last: dict[str, int] = {}5    l = 06    best = 07    for r, ch in enumerate(s):8        if ch in last and last[ch] >= l:9            l = last[ch] + 1  # shrink past previous ch10        last[ch] = r11        best = max(best, r - l + 1)12    return best1314# Dry-run "abba": r=0 a; r=1 b; r=2 b -> l=2; r=3 a -> l=1? last[a]=0 < l=2 so l stays 2;15# actually last[a] updated careful: at r=3, last[a]=0 < l=2, best max with len 1…16# Trace fully in interview — off-by-one here is common.

The “at most K” template

Goal: number of (or longest) subarrays with at most K distinct integers. Generic template: freq map + distinct counter; expand R; while distinct > K, decrement freq[a[L]] and maybe distinct, L++. For longest: track max(R−L+1). For count of subarrays: add (R−L+1) every time you fix R (every subarray ending at R with L..R valid). Exactly K distinct = atMost(K) − atMost(K−1).
python
1AT MOST K DISTINCT — count subarrays (template gold)23from collections import defaultdict45def at_most_k_distinct(a: list[int], k: int) -> int:6    if k < 0:7        return 08    freq: dict[int, int] = defaultdict(int)9    l = 010    distinct = 011    ans = 012    for r, x in enumerate(a):13        if freq[x] == 0:14            distinct += 115        freq[x] += 116        while distinct > k:17            freq[a[l]] -= 118            if freq[a[l]] == 0:19                distinct -= 120            l += 121        ans += r - l + 1  # all subarrays ending at r22    return ans2324def exactly_k_distinct(a, k):25    return at_most_k_distinct(a, k) - at_most_k_distinct(a, k - 1)

Minimum window substring (harder variable window)

Find smallest window in s covering all chars of t (with multiplicity). Need freq of t, a “missing” or “formed” counter, expand R until valid, then shrink L while valid, track best. This is the production cousin of “smallest log span that contains all error codes of interest.” Complexity O(|s| + |t|) with alphabet maps.
Rate-limit metaphor: a fixed window counter “max 100 requests per 60s” is fixed window on a time axis; a token bucket is a different algorithm (capstone). In interviews, if they say “longest period where condition holds,” think variable window; if “exactly last K events,” fixed.

When the left pointer moves — force the sentence

Build the habit: every time R advances, ask “is [L,R] still valid?” If not, advance L until it is (or until L>R breaks). For max-length problems you track best when valid; for min-length you shrink while valid and track best; for count problems you add (R−L+1) when [L,R] is the maximal valid window ending at R. Mixing those three update rules is the #1 silent bug in window interviews.
Grid/string hybrids (minimum window covering t) need a second counter: how many unique requirements are currently satisfied. Increment “formed” when a char’s count hits the need; decrement when shrink breaks it. Narrate formed/need like a refcount — production engineers already do this for resource leases.
python
1MIN WINDOW COVERING t — formed/need counters (skeleton)23from collections import Counter45def min_window(s: str, t: str) -> str:6    need = Counter(t)7    missing = len(t)8    best = (0, float("inf"))  # start, end exclusive9    l = 010    for r, ch in enumerate(s):11        if need[ch] > 0:12            missing -= 113        need[ch] -= 114        while missing == 0:15            if r + 1 - l < best[1] - best[0]:16                best = (l, r + 1)17            need[s[l]] += 118            if need[s[l]] > 0:19                missing += 120            l += 121    return "" if best[1] == float("inf") else s[best[0]:best[1]]2223# O(|s|+|t|). Dry-run s="ADOBECODEBANC", t="ABC" in the interview.
Sliding Window Maximum / window technique family — NeetCode style explainersNeetCode

Interview prep

Window rounds reward a one-sentence validity predicate and a correct L-move rule. Practice deriving at-most-K from scratch without looking at a template.
  1. 01“How do you recognize sliding window?” → contiguous subarray/substring + monotonic constraint on the segment.
  2. 02“When does L move?” → while window invalid (or while you can shrink and stay optimal for min-window).
  3. 03“Exactly K distinct?” → atMost(K) − atMost(K−1); explain why each ending index contributes r−l+1.
  4. 04“Fixed vs variable?” → fixed size K vs grow/shrink on predicate.
  5. 05“Min window covering t?” → expand until cover, shrink while cover, track best bounds.
  6. 06“Complexity?” → O(n) amortized if L,R each move ≤n and updates O(1)/O(σ).
  7. 07“Production story?” → rolling latency, session length with ≤K error types, rate windows.
  8. 08“Common bug?” → forgetting to update freq when jumping L; off-by-one on best length.
  9. 09"Min window state?" -> need map + missing count; expand; shrink while valid; track best.
  10. 10"Why deque for window max?" -> expire front; pop back; O(1) max; heap lacks O(1) delete.
  11. 11"Exactly K?" -> atMost(K) - atMost(K-1).
  12. 12"Rate limit window?" -> timestamp queue; pop expired; reject if len >= limit.
Name the validity predicate in one sentence before you touch L and R. If the predicate is not monotonic, stop and reconsider the pattern.
articleSliding Window pattern overviewAlgoMasterdocsNeetCode — Longest Substring Without Repeating CharactersNeetCodearticleLeetCode Discuss — Sliding Window templatesLeetCode DiscussarticleTech Interview Handbook study planTech Interview Handbook

Hard templates: min window + sliding max

Spoken catalog. Max sum K: fixed window. Longest no-repeat: last-seen jump L. Character replacement: windowSize - maxFreq <= K. Permutation in string: fixed window + freq vector. Min window substring: need/have; expand until satisfied; shrink while valid. Window maximum: monotonic deque (not heap — cannot expire arbitrary indices in O(1)). Exactly K distinct: atMost(K)-atMost(K-1). Max consecutive ones III: at most K zeros. Production: 60s rate limiter timestamps, Prometheus rolling metrics, TCP receive window. Before you code any window, force three sentences: (1) what is the validity predicate, (2) what state updates when R expands, (3) when and how L advances. Fixed windows always move L with R after the first K; variable windows only move L when the invariant breaks (or while it still holds, for min-window shrink). Count-of-subarrays variants add (R-L+1) for every fixed R when every suffix of the window is valid. Interviewers plant abba, K=0, and all-identical strings to catch last-seen and shrink bugs.
python
1MINIMUM WINDOW SUBSTRING — need/have (LC 76)23from collections import Counter45def min_window(s: str, t: str) -> str:6    if not t or not s:7        return ""8    need = Counter(t)9    missing = len(t)10    best_l, best_len = 0, float("inf")11    l = 012    for r, ch in enumerate(s):13        if need[ch] > 0:14            missing -= 115        need[ch] -= 116        while missing == 0:17            if r - l + 1 < best_len:18                best_l, best_len = l, r - l + 119            need[s[l]] += 120            if need[s[l]] > 0:21                missing += 122            l += 123    return "" if best_len == float("inf") else s[best_l:best_l + best_len]2425# Dry-run ADOBECODEBANC / ABC -> BANC. O(|s|+|t|).
python
1SLIDING WINDOW MAXIMUM — monotonic deque23from collections import deque45def max_sliding_window(nums: list[int], k: int) -> list[int]:6    dq: deque[int] = deque()  # indices, nums decreasing7    out: list[int] = []8    for i, x in enumerate(nums):9        while dq and dq[0] <= i - k:10            dq.popleft()11        while dq and nums[dq[-1]] <= x:12            dq.pop()13        dq.append(i)14        if i >= k - 1:15            out.append(nums[dq[0]])16    return out  # O(n) amortized; each index enter/leave once
Graders + tiers. Name the invariant; pick fixed vs variable vs atMost vs deque; L never retreats; verify K=0, K>=n, all-same, all-distinct. FAANG: non-trivial variable windows as follow-ups. India OA: fixed-window staples. AI lab: fault-tolerant 60s aggregator on TB/min streams with watermarks and late events. If your first instinct is nested loops on a contiguous constraint, pause and name the window family — that self-interrupt is a senior signal.
Longest Substring Without Repeating — NeetCodeNeetCodeSliding Window Technique — takeUforwardtakeUforwardarticleSliding Window cheatsheet — TIHTech Interview Handbook

Checkpoint

“Longest subarray with at most K distinct integers.” You start writing a DP table dp[i][k]. Better first move?

AContinue DP — at most K always needs DPBSliding window with freq map: expand R, while distinct > K advance L; track max lengthCSort the array first so distinct runs are grouped
Sign up free to answer and see why

Checkpoint

In the count-subarrays at-most-K template, why add (r − l + 1) for each r?

AIt is an arbitrary heuristic that happens to pass testsBWith [l,r] the longest valid window ending at r, every start in [l,r] is also valid ending at rCBecause there are r−l+1 distinct values
Sign up free to answer and see why

Checkpoint

Minimum window substring: window is valid covering t. Next operation for global minimum?

AImmediately expand R further to find a bigger windowBShrink L while still valid, update best; only then expand R againCReset L to 0 and start over from next R
Sign up free to answer and see why

Checkpoint

Production prompt: longest contiguous session of events with ≤3 error codes. Which map?

AGraph BFS on error codesBVariable sliding window on the event stream with K=3 distinct error codesCFixed window of size 3 events
Sign up free to answer and see why

Checkpoint

You need number of subarrays with exactly 2 distinct integers. Cleanest approach?

AatMost(2) − atMost(1)BOnly atMost(2)CNested loops only — no closed form
Sign up free to answer and see why

Can you derive the at-most-K template from scratch and dry-run L moves on a 6-element example?

New to itGetting thereConfident

Takeaways

  • Contiguous + monotonic constraint → sliding window before DP.
  • Fixed K vs variable L/R; validity predicate is the design center.
  • atMost(K) − atMost(K−1) for exactly K; add (r−l+1) when counting.
  • Min window: expand to valid, shrink while valid, track best.
  • Production: rolling latency, rate windows, session segments.

Next: hashmaps, prefix sums, and subarray sum K — frequency maps that turn O(n²) into O(n).

Sources

Free to read · better with Enzo

Learn it with Enzo

Save your progress, answer the checkpoints, and let Enzo quiz you on what you just read.

Continue with EnzoSign up free