Sliding Window

If a problem asks for something about every contiguous subarray or substring of size K, or the longest/shortest contiguous run that satisfies some condition, recomputing from scratch for every start index costs $O(n \cdot k)$ or worse. A sliding window reuses the work from the previous window instead of redoing it — one pointer expands the window, another shrinks it, and the whole array is visited only once.

This is the single most-asked array pattern in big-tech phone screens. Get the two templates below into muscle memory and a large slice of the Medium tier becomes mechanical.

What you’ll learn

Fixed-size windows: slide a constant-width window across the array.
Variable-size windows: expand with a right pointer, shrink with a left pointer whenever a condition breaks.
The expand/shrink template that covers both.
The five variants interviewers actually build on top of the template.
Four real LeetCode problems solved here in the browser (643, 3, 209, 424), plus a graded ladder up to 76 and 992 (Hard).

The cue

The pattern

Fixed-size window — the window width k never changes. Add the incoming element, drop the outgoing one, track the best result.

Variable-size window — right always expands the window by one. left only moves forward, shrinking the window, while some condition is violated (window sum too big, a character count too high, and so on).

sliding_window_template.py

def fixed_window_template(arr, k):
    window_sum = sum(arr[:k])
    best = window_sum
    for right in range(k, len(arr)):
        window_sum += arr[right]          # add the new right edge
        window_sum -= arr[right - k]      # drop the old left edge
        best = max(best, window_sum)
    return best
 
 
def variable_window_template(arr, limit):
    left = 0
    window_sum = 0
    best_length = 0
    for right in range(len(arr)):
        window_sum += arr[right]                 # always expand right
        while window_sum > limit:                # shrink while invalid
            window_sum -= arr[left]
            left += 1
        best_length = max(best_length, right - left + 1)
    return best_length
 
 
print(fixed_window_template([2, 1, 5, 1, 3, 2], 3))
print(variable_window_template([1, 2, 1, 0, 1, 1, 0], 4))

How it works

The key insight: moving the window one step to the right only changes two elements — one leaves, one enters. There’s no reason to re-sum (or re-scan) the whole window every time, so the total work across all positions stays $O(n)$ instead of $O(n \cdot k)$ .

arrayA window of width 3 sliding across an arrayO(n) · fixed width

k = 3

201152133425

1def max_sum_fixed(arr, k):2    window = sum(arr[:k])3    best = window4    for right in range(k, len(arr)):5        window += arr[right]        # element enters6        window -= arr[right - k]    # element leaves7        best = max(best, window)8    return best

window8best8

seedSeed the first window: sum of the first 3 elements is 8.

1/8

Step through it: at every slide exactly one cell turns green (entering) and one turns red (leaving). Everything between them is reused, never re-summed -- that reuse is the entire pattern.

Now the variable-width version on LC 209. Watch the left pointer specifically: it moves only forward, and it is the reason the nested while does not make this $O(n^2)$ .

arrayShrinking to the shortest window that reaches 7LC 209 · shortest-valid

sum 2

203112234435

leftright

1def min_len_at_least(arr, target):2    left = total = 03    best = float('inf')4    for right in range(len(arr)):5        total += arr[right]              # expand6        while total >= target:           # valid — try to shrink7            best = min(best, right - left + 1)8            total -= arr[left]9            left += 110    return 0 if best == float('inf') else best

total2target7best∞

expandExpand: 2 joins the window, sum becomes 2. Still short of 7.

1/17

Scrub back and forth across a shrink phase. The window is measured BEFORE each shrink step, because as soon as it is valid it is a candidate -- that ordering is what makes this the shortest-valid variant rather than the longest-valid one.

Dry run

Trace LC 209 with target = 7, nums = [2, 3, 1, 2, 4, 3] by hand before you trust the code. In an interview you will be asked to do exactly this on a whiteboard, and the table below is the shape your answer should take.

Step	`right`	enters	`total`	valid?	action	`left`	`best`
1	0	2	2	no	expand	0	∞
2	1	3	5	no	expand	0	∞
3	2	1	6	no	expand	0	∞
4	3	2	8	yes	record len 4, drop `nums[0]=2`	1	4
5	3	—	6	no	stop shrinking, expand	1	4
6	4	4	10	yes	record len 4, drop `nums[1]=3`	2	4
7	4	—	7	yes	record len 3, drop `nums[2]=1`	3	3
8	4	—	6	no	stop shrinking, expand	3	3
9	5	3	9	yes	record len 3, drop `nums[3]=2`	4	3
10	5	—	7	yes	record len 2, drop `nums[4]=4`	5	2
11	5	—	3	no	stop; loop ends	5	2

Two things to read off that table:

left took 5 steps and right took 6 across the entire run — 11 pointer moves for a 6-element array, not 36. That is the amortised argument, stated concretely.
best improved at steps 4, 7 and 10, always inside the shrink loop. Move that measurement outside the loop and you get 3 instead of 2.

Time and space complexity

Approach	Time	Space
Recompute every window from scratch	$O(n \cdot k)$	$O(1)$
Sliding window (fixed or variable)	$O(n)$	$O(1)$ to $O(k)$ (for a char/count map)

Each element enters the window once and leaves at most once, so left and right together take at most $2n$ steps total — that’s the $O(n)$ guarantee even though there’s a nested while.

The variant map

Almost every sliding-window problem is the template plus one of these five mutations. Recognising which mutation you’re being handed is most of the work.

Variant	What changes in the template	Canonical problem
Fixed width, running aggregate	No `while` at all — one add, one subtract per step	643 Maximum Average Subarray I
Longest valid window	Shrink while invalid, then record `right - left + 1`	3 Longest Substring Without Repeating Characters
Shortest valid window	Shrink while valid — the loop condition flips	209 Minimum Size Subarray Sum
Window + frequency map	Track counts in a dict; validity is a property of the counts	424 Longest Repeating Character Replacement
Count subarrays, not length	Add `right - left + 1` to a total instead of taking a max	992 Subarrays with K Different Integers

Practice — real LeetCode problems

Each exercise below is the actual LeetCode problem, with the real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected list. Then paste the same code into leetcode.com to clear the hidden tests.

LC 643 — Maximum Average Subarray I · Easy

Problem. Given an integer array nums and an integer k, find a contiguous subarray of length exactly k with the maximum average, and return that average.

Constraints. 1 <= k <= len(nums) <= 10^5, -10^4 <= nums[i] <= 10^4. Answers within 10^-5 are accepted.

Examples. nums = [1,12,-5,-6,50,3], k = 4 gives 12.75 · nums = [5], k = 1 gives 5.0

Editorial — approach, complexity, follow-ups

Sum the first k elements once. Then each step the window moves right by one, which changes exactly two elements: nums[right] enters and nums[right - k] leaves. So the new sum is window + nums[right] - nums[right - k] in $O(1)$ .

Time $O(n)$ — one pass. Space $O(1)$ .

Two details that matter in an interview:

Track the sum, not the average. Comparing sums avoids n divisions and avoids accumulating floating-point error. Divide once at the end.
Negative numbers are fine here. The window is fixed width, so there is no shrink decision that could be fooled by negatives. This is exactly why 643 is Easy and 209 (variable width) is Medium.

Follow-ups you should expect: “What if k can change between queries?” — precompute a prefix-sum array, then any window is one subtraction. “What if the array is a stream you can’t index backwards?” — keep the last k values in a collections.deque(maxlen=k).

LC 3 — Longest Substring Without Repeating Characters · Medium

Problem. Given a string s, return the length of the longest substring without repeating characters.

Constraints. 0 <= len(s) <= 5 * 10^4, s is ASCII.

Examples. "abcabcbb" gives 3 ("abc") · "bbbbb" gives 1 · "pwwkew" gives 3 ("wke" — not the subsequence "pwke")

"dvdf" is the input that breaks naive attempts, so step through it before you write anything. Note where left lands at right = 2:

arrayWhy left must jump, and why it must never jump backwardsLC 3 · longest-valid

len 1

d0v1d2f3

leftright

1def longest_unique(s):2    seen = {}          # char -> last index3    left = best = 04    for right, ch in enumerate(s):5        if ch in seen and seen[ch] >= left:6            left = seen[ch] + 1      # jump past the duplicate7        seen[ch] = right8        best = max(best, right - left + 1)9    return best

windowdbest1

expandWindow "d" has 1 distinct characters — a new best.

1/6

At right = 2 the duplicate 'd' sits at index 0, so left jumps to 1 in one move rather than shrinking step by step. The map keeps LAST INDEX, not a count -- that is what makes the jump possible.

Editorial — approach, complexity, follow-ups

Expand right over every character. Maintain last[ch] = the most recent index of each character. When the incoming character was last seen at or after left, it is inside the current window, so the window must start just past it: left = last[ch] + 1.

Time $O(n)$ — left never moves backwards. Space $O(\min(n, |\Sigma|))$ where $|\Sigma|$ is the alphabet size (at most 128 for ASCII).

The "dvdf" case in the tests is the one that catches naive solutions. Walk it: at right = 2 we see d again with last['d'] = 0, so left jumps to 1. At right = 3 (f), the window is "vdf" — length 3. A solution that resets left = 0 or that removes characters one at a time without the at-or-after guard returns 2 here.

Follow-ups you should expect: “Return the substring, not its length” — also store best_left, then slice. “At most k distinct characters instead of zero repeats” — swap the jump for a frequency dict and a shrink loop on len(count) > k (that is LC 340). “What if the alphabet is Unicode?” — the dict already handles it; only the space bound changes.

LC 209 — Minimum Size Subarray Sum · Medium

Problem. Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray whose sum is at least target. If there is no such subarray, return 0.

Constraints. 1 <= len(nums) <= 10^5, 1 <= nums[i] <= 10^4.

Examples. target = 7, nums = [2,3,1,2,4,3] gives 2 ([4,3]) · target = 4, nums = [1,4,4] gives 1 · target = 11, nums = [1,1,1,1,1,1,1,1] gives 0

Editorial — approach, complexity, follow-ups

This is the mirror image of LC 3, and the difference is worth stating out loud in an interview:

Longest valid window — shrink while invalid, measure after the loop.
Shortest valid window — while valid: measure, then shrink.

Here, as soon as the window sum reaches target we have a valid answer, so we record it and immediately try to make it smaller by dropping nums[left]. We keep going until the window is too small again.

Time $O(n)$ — each index is added once and removed at most once. Space $O(1)$ .

Why “positive integers” is load-bearing. With all-positive values, window grows monotonically as right advances and shrinks monotonically as left advances. That is exactly the monotonicity the pattern needs. If nums could contain negatives, shrinking might increase the sum, the invariant collapses, and you need prefix sums plus a monotonic deque instead — which is LC 862 (Hard), and a very common follow-up.

Follow-ups you should expect: “Do it in $O(n \log n)$ ” — prefix sums plus a binary search for each start index (an alternate solution the problem explicitly asks for). “What if values can be negative?” — see LC 862. “Return the subarray itself” — track best_left alongside best.

LC 424 — Longest Repeating Character Replacement · Medium

Problem. You may change at most k characters of s to any uppercase English letter. Return the length of the longest substring containing the same letter that you can obtain.

Constraints. 1 <= len(s) <= 10^5, s is uppercase A-Z, 0 <= k <= len(s).

Examples. s = "ABAB", k = 2 gives 4 · s = "AABABBA", k = 1 gives 4 ("AABA" becomes "AAAA")

arrayValidity as a property of the frequency mapLC 424 · window + counts

0 to replace

A0A1B2A3B4B5A6

leftright

1def char_replacement(s, k):2    count = {}3    left = best = max_freq = 04    for right, ch in enumerate(s):5        count[ch] = count.get(ch, 0) + 16        max_freq = max(max_freq, count[ch])7        while (right - left + 1) - max_freq > k:8            count[s[left]] -= 19            left += 110        best = max(best, right - left + 1)11    return best

size1maxFreq1toReplace0k1

expand'A' enters. The window is size 1 and its most common character appears 1 times, so 0 characters would need replacing.

1/11

The chips under the row are the frequency map. A window is valid when (its size) minus (the tallest chip) is at most k -- so validity is never about positions, only about counts.

Editorial — approach, complexity, follow-ups

The reframe that unlocks this problem: inside any window, the cheapest way to make every character the same is to keep the most frequent character and replace all the others. So the number of replacements a window needs is

$\text{needed} = (\text{window length}) - \max_{c} \text{count}[c]$

and the window is valid exactly when needed is at most k.

Time $O(n)$ . Space $O(|\Sigma|) = O(26) = O(1)$ .

When we shrink, we decrement count[s[left]] but leave max_freq alone — so max_freq can be stale (higher than any actual count in the current window). That looks like a bug and is not, for a precise reason: best only ever grows, and a window can only produce a new best if it has a genuinely higher max_freq than anything seen before. A stale max_freq can make us overestimate the current window’s validity, but never enough to record a best larger than some real window’s size. Dropping the recomputation turns an $O(26n)$ solution into a clean $O(n)$ one.

If this makes you uncomfortable in an interview, say so and write max_freq = max(count.values()) inside the shrink branch. $O(26n)$ passes every test, and explaining why you chose the safe version reads better than silently shipping a trick you can’t justify.

Note also the single shrink step rather than a loop: because we only ever need to recover from one character entering, one shrink per iteration is enough. The window consequently never shrinks in size, and best is just the largest size it ever reached.

Follow-ups you should expect: “What if the alphabet is arbitrary?” — the dict already handles it; space becomes $O(|\Sigma|)$ . “Return the actual substring” — track best_left. “What if you can only replace with a specific letter?” — the problem collapses to LC 1004 Max Consecutive Ones III, the same template with a simpler validity test.

LeetCode problem set

Generated from the problem database, so every entry carries its sheet membership and reported companies. Progress is saved in this browser.

Work down the list. The template barely changes — the validity condition is what each problem is really testing.

18 problems

2 easy12 medium4 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

Unsolved onlyImport

219Contains Duplicate IIeasyFixed window of size `k` holding a `set`LeetCode Top Interview 150
643Maximum Average Subarray IeasyThe plain fixed-width template
3Longest Substring Without Repeating CharactersmediumLongest-valid, jump `left` past duplicatesNeetCode 150Blind 75LeetCode Top Interview 150amazongooglemetamicrosoftbloomberg
209Minimum Size Subarray SummediumShortest-valid -- the loop condition flipsLeetCode Top Interview 150
340Longest Substring with At Most K Distinct CharacterspremiummediumThe generalisation of 904 to any `k`
424Longest Repeating Character ReplacementmediumValidity is a property of the frequency mapNeetCode 150Blind 75
438Find All Anagrams in a Stringmedium567 but collect every match instead of the first
567Permutation in StringmediumFixed width + compare two frequency mapsNeetCode 150
904Fruit Into Basketsmedium"At most 2 distinct" -- shrink on `len(count) > 2`
1004Max Consecutive Ones IIImedium424 with a two-symbol alphabet -- count zeros in window
1456Maximum Number of Vowels in a Substring of Given LengthmediumFixed width, but the aggregate is a predicate count
1493Longest Subarray of 1's After Deleting One ElementmediumExactly one zero allowed, then subtract 1
1838Frequency of the Most Frequent ElementmediumSort first, then window on the cost to level up
2461Maximum Sum of Distinct Subarrays With Length KmediumFixed width **and** a distinctness constraint
76Minimum Window SubstringhardShortest-valid + a `missing` counter to test validity in $O(1)$NeetCode 150Blind 75LeetCode Top Interview 150metaamazongoogleuber
30Substring with Concatenation of All WordshardRun the window once per offset within a word lengthLeetCode Top Interview 150
220Contains Duplicate IIIhard
992Subarrays with K Different Integershard**Count**, via `atMost(k) - atMost(k-1)`

Interview follow-ups

The template is table stakes. These are the questions that separate a “pass” from a “strong hire” on a sliding-window problem.

They ask	What they’re checking	The answer
“Why is this $O(n)$ when there’s a nested loop?”	Amortised reasoning	`left` never moves backwards, so it advances at most `n` times in total across the whole run — $2n$ pointer moves, not $n \times n$
“What if the numbers can be negative?”	Whether you know the pattern’s limits	The window invariant breaks; switch to prefix sums + hash map (counting) or + monotonic deque (LC 862)
“Can you do it in one pass with $O(1)$ space?”	Whether the map is really needed	Yes when the alphabet is bounded — a 26-slot list beats a dict, and $O(26)$ is $O(1)$
“How would you handle a stream?”	Practical modelling	`deque(maxlen=k)` for fixed windows; variable windows need the tail retained, so state the memory cost honestly
“Return the window, not its size”	Care with bookkeeping	Track `best_left` whenever you update `best`, then slice at the end

Edge-case checklist

Say these out loud before you start coding — interviewers score the clarifying questions, and half of them are real test cases:

Empty input — s = "" or nums = []. Does the loop body ever run? Is the initial best a legal return value?
k larger than the input — for fixed windows, sum(nums[:k]) will silently under-fill instead of erroring. Clarify or guard.
k = 0 — a legal input in 424 and 1004. Does the validity test still hold?
No valid window exists — LC 209 must return 0, not float("inf"). This is the single most common failed submission on that problem.
All elements identical — "bbbbb", [1,1,1,1]. Usually the case where an off-by-one in the shrink loop shows up.
Window of size exactly 1 — does right - left + 1 give 1, not 0?
Negative numbers and zeros — legal in 643 (fixed width, harmless), fatal to the assumption in 209 (variable width). Check which you have.

Self-check

Answer these before moving on. If a question needs more than a few seconds, the section it came from is worth a second read.

pch.quizTag Sliding window — self-check

An array contains negative numbers and you need the shortest subarray with sum at least target. Is a sliding window correct?

pch.quizShowAnswer

B — No — negatives break the monotonicity the shrink decision relies on — Shrinking must be guaranteed to reduce the window sum. With a negative value at the left edge, dropping it INCREASES the sum, so 'too big → shrink' is no longer sound. Sorting is not available either, because the subarray must stay contiguous. Use prefix sums plus a monotonic deque (LC 862).
For a LONGEST-valid-window problem, where do you record the answer?

pch.quizShowAnswer

B — After the shrink loop has finished — The window is only guaranteed valid once the shrink loop has exited, so that is the only safe place to measure it. Shortest-valid is the mirror image: there the window is valid on entry to the loop, so you measure before each shrink.
In LC 424, max_freq is never decreased when the window shrinks. Why is the answer still correct?

pch.quizShowAnswer

C — A stale max_freq can only overestimate the current window, and best only grows when some real window is genuinely larger — A too-large max_freq makes the validity test too permissive, so the window may not shrink when it 'should'. But best is only ever updated to a larger size, and reaching a larger size requires a genuinely higher real max_freq. So no overestimate can produce an answer bigger than a real window. Recomputing max(count.values()) is the safe O(26n) alternative worth mentioning out loud.
The pattern has a nested while loop inside a for loop. Why is it O(n) rather than O(n²)?

pch.quizShowAnswer

B — left never moves backwards, so across the whole run it advances at most n times in total — This is an amortised argument, not a per-iteration one. The inner loop can run many times on a single iteration, but the total number of left-advances over the entire algorithm is capped at n. Combined with right's n advances that is at most 2n pointer moves.
You need to count subarrays with EXACTLY k distinct integers. What is the standard move?

pch.quizShowAnswer

B — Compute atMost(k) − atMost(k − 1) — 'At most k' is an easy monotonic window; 'exactly k' is not. Subtracting the two at-most counts turns LC 992 (Hard) into LC 904 (Medium) run twice. The same subtraction trick recurs across counting problems.

Recall card

Five lines. If you can reproduce these from memory a week from now, the pattern is yours.

Cue — “contiguous” and (“size k” or longest/shortest satisfying a condition) and the condition is monotonic in window size.
Invariant — left is monotonically non-decreasing; the window [left, right] is the only candidate under consideration.
Template — right always expands; while the condition says so, move left. Longest → shrink while invalid, measure after. Shortest → measure, then shrink while valid.
Complexity — $O(n)$ time by amortisation ( $\le 2n$ pointer moves), $O(1)$ space, or $O(\min(n, |\Sigma|))$ with a count map.
Fails when — values can be negative (sum windows), or the condition is not monotonic. Reach for prefix sums + hash map, or a monotonic deque.

Recap

Sliding window avoids re-scanning overlapping work: only the entering and leaving elements change the running state each step.
Fixed-size: constant width, slide across — one add, one subtract.
Variable-size: right always expands, left shrinks while the window is invalid — total work still $O(n)$ thanks to amortized pointer movement.
Longest valid means shrink-while-invalid then measure. Shortest valid means measure-then-shrink while still valid. Getting these backwards is the number-one bug.
The pattern needs a monotonic validity condition. Negative numbers break sum-based windows — reach for prefix sums instead.
Cue: “contiguous subarray/substring” + “size K” or “longest/shortest satisfying a condition” means sliding window.

Next: Monotonic Deque — what to reach for when the window needs its maximum rather than its sum, and the $O(n)$ trick behind LC 239.

pch.coffeeTagline

pch.coffeeCta

pch.feedbackHeading

pch.feedbackSubheading