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 rightright pointer, shrink with a leftleft 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 kk never changes. Add the incoming element, drop the outgoing one, track the best result.

Variable-size window — rightright always expands the window by one. leftleft 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))

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)$ .

sketch A window of width 3 sliding across an array p5.js

Only the entering (green) and leaving (red) elements change the running sum each step -- the middle elements are reused, never recomputed.

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 leftleft and rightright together take at most $2n$ steps total — that’s the $O(n)$ guarantee even though there’s a nested whilewhile.

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 `whilewhile` at all — one add, one subtract per step	643 Maximum Average Subarray I
Longest valid window	Shrink while invalid, then record `right - left + 1right - 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 + 1right - 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 numsnums and an integer kk, find a contiguous subarray of length exactly kk with the maximum average, and return that average.

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

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

Editorial — approach, complexity, follow-ups

Sum the first kk elements once. Then each step the window moves right by one, which changes exactly two elements: nums[right]nums[right] enters and nums[right - k]nums[right - k] leaves. So the new sum is window + nums[right] - nums[right - k]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 nn 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 kk 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 kk values in a collections.deque(maxlen=k)collections.deque(maxlen=k).

LC 3 — Longest Substring Without Repeating Characters · Medium

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

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

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

Editorial — approach, complexity, follow-ups

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

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

The "dvdf""dvdf" case in the tests is the one that catches naive solutions. Walk it: at right = 2right = 2 we see dd again with last['d'] = 0last['d'] = 0, so leftleft jumps to 11. At right = 3right = 3 (ff), the window is "vdf""vdf" — length 3. A solution that resets left = 0left = 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_leftbest_left, then slice. “At most kk distinct characters instead of zero repeats” — swap the jump for a frequency dict and a shrink loop on len(count) > klen(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 numsnums and a positive integer targettarget, return the minimal length of a contiguous subarray whose sum is at least targettarget. If there is no such subarray, return 00.

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

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

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 targettarget we have a valid answer, so we record it and immediately try to make it smaller by dropping nums[left]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, windowwindow grows monotonically as rightright advances and shrinks monotonically as leftleft advances. That is exactly the monotonicity the pattern needs. If numsnums 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_leftbest_left alongside bestbest.

LC 424 — Longest Repeating Character Replacement · Medium

Problem. You may change at most kk characters of ss 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^51 <= len(s) <= 10^5, ss is uppercase A-Z, 0 <= k <= len(s)0 <= k <= len(s).

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

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 kk.

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

When we shrink, we decrement count[s[left]]count[s[left]] but leave max_freqmax_freq alone — so max_freqmax_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: bestbest only ever grows, and a window can only produce a new bestbest if it has a genuinely higher max_freqmax_freq than anything seen before. A stale max_freqmax_freq can make us overestimate the current window’s validity, but never enough to record a bestbest 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())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 bestbest 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_leftbest_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

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

#	Problem	Difficulty	The twist
643	Maximum Average Subarray I	Easy	The plain fixed-width template
219	Contains Duplicate II	Easy	Fixed window of size `kk` holding a `setset`
1456	Maximum Number of Vowels in a Substring of Given Length	Medium	Fixed width, but the aggregate is a predicate count
3	Longest Substring Without Repeating Characters	Medium	Longest-valid, jump `leftleft` past duplicates
209	Minimum Size Subarray Sum	Medium	Shortest-valid — the loop condition flips
424	Longest Repeating Character Replacement	Medium	Validity is a property of the frequency map
1004	Max Consecutive Ones III	Medium	424 with a two-symbol alphabet — count zeros in window
567	Permutation in String	Medium	Fixed width + compare two frequency maps
438	Find All Anagrams in a String	Medium	567 but collect every match instead of the first
904	Fruit Into Baskets	Medium	“At most 2 distinct” — shrink on `len(count) > 2len(count) > 2`
1493	Longest Subarray of 1’s After Deleting One Element	Medium	Exactly one zero allowed, then subtract 1
1838	Frequency of the Most Frequent Element	Medium	Sort first, then window on the cost to level up
2461	Maximum Sum of Distinct Subarrays With Length K	Medium	Fixed width and a distinctness constraint
340	Longest Substring with At Most K Distinct Characters	Medium · Premium	The generalisation of 904 to any `kk`
76	Minimum Window Substring	Hard	Shortest-valid + a `missingmissing` counter to test validity in $O(1)$
992	Subarrays with K Different Integers	Hard	Count, via `atMost(k) - atMost(k-1)atMost(k) - atMost(k-1)`
30	Substring with Concatenation of All Words	Hard	Run the window once per offset within a word length

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	`leftleft` never moves backwards, so it advances at most `nn` 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)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_leftbest_left` whenever you update `bestbest`, 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 = ""s = "" or nums = []nums = []. Does the loop body ever run? Is the initial bestbest a legal return value?
kk larger than the input — for fixed windows, sum(nums[:k])sum(nums[:k]) will silently under-fill instead of erroring. Clarify or guard.
k = 0k = 0 — a legal input in 424 and 1004. Does the validity test still hold?
No valid window exists — LC 209 must return 00, not float("inf")float("inf"). This is the single most common failed submission on that problem.
All elements identical — "bbbbb""bbbbb", [1,1,1,1][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 + 1right - left + 1 give 11, not 00?
Negative numbers and zeros — legal in 643 (fixed width, harmless), fatal to the assumption in 209 (variable width). Check which you have.

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: rightright always expands, leftleft 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.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Sliding Window

What you’ll learn

The cue

The pattern

How it works

Time and space complexity

The variant map

Practice — real LeetCode problems

LC 643 — Maximum Average Subarray I · Easy

LC 3 — Longest Substring Without Repeating Characters · Medium

LC 209 — Minimum Size Subarray Sum · Medium

LC 424 — Longest Repeating Character Replacement · Medium

LeetCode problem set

Interview follow-ups

Edge-case checklist

Recap

Was this page helpful?