Fixed-Size Sliding Window

What problem this solves

Whenever a problem statement fixes a window length up front — "subarray of length k", "substring of length k", "every window of size k" — the naive instinct is to recompute something (a sum, a count, a max) from scratch for every one of the n - k + 1 starting positions. That's O(n·k) at best. A fixed-size sliding window notices that consecutive windows overlap in k - 1 elements, so instead of recomputing you can update incrementally: add the element entering on the right, remove the element leaving on the left, and derive the new window's answer from the old one in O(1).

This is the simplest member of the Sliding Window family (the other is Variable-Size Sliding Window, covered next) and a direct specialization of the same-direction pointer discipline you saw in Two Pointers — the difference is that here you explicitly track a window and its aggregate state, not just two indices.

How to recognize it in a problem statement

• The window size k is given explicitly as an input, and never changes during the algorithm.
• Phrases like "every contiguous subarray/substring of length k", "the maximum/minimum/sum/average over any window of size k", or "check if any window of size k satisfies property P".
• Contrast with Variable-Size Sliding Window: if the problem instead asks for the longest or shortest subarray satisfying some condition — the size itself is unknown and is what you're solving for — you want the variable-size version, not this one.

Mechanics: the expand-and-shift template

The shape is a single pass with two logical phases per iteration: grow the window by one on the right, then — once it has reached size k — record the answer and shrink it by one on the left. Because growth and shrinkage always happen together once the window is "full," there's no separate inner loop; it's a plain for loop with an if.

Two invariants to hold onto:

• The window is always arr[right - k + 1 .. right] once right >= k - 1. Off-by-one errors here (using right - k instead of right - k + 1) are the single most common bug in this pattern.
• State is updated incrementally, never recomputed. If your "add" and "remove" operations aren't both O(1) (or O(alphabet size) for frequency maps), you've lost the benefit of the pattern and should ask whether a different technique fits better.

Common variations

Window state	Typical operation	Example use case
Running sum / product	+= on entry, -= on exit	Max/min sum of a fixed-size subarray
Fixed-size frequency map (array of 26 or hash map)	increment on entry, decrement on exit	Anagram/permutation detection, vowel counts
Monotonic deque of indices	push while popping smaller/larger from the back, pop stale front	Max/min of every window (see below)
Running distinct-count via a map	increment count; if it was 0, distinct += 1; symmetric on exit	Distinct elements per fixed window

The one case that breaks the simple template: finding the maximum (or minimum) of every window of size k — LeetCode calls this "Sliding Window Maximum." A naive O(1)-per-step update doesn't work because when the current max leaves the window on the left, you don't know the second-largest without rescanning. The fix is to maintain a monotonic deque of indices (decreasing values front-to-back): pop from the back while the incoming element is larger (those elements can never be the max again), push the new index, and pop from the front if it has fallen out of the window. This is the same monotonic-deque/monotonic-stack idea you'll formalize in the Monotonic Stack topic — treat this problem as your first hands-on preview of it.

Complexity analysis

• Time: O(n). Every index enters the window exactly once (via the right pointer) and leaves exactly once (via the implicit left = right - k + 1), so total work across the whole run is O(n) regardless of k. For the monotonic-deque variant, each index is pushed once and popped at most once, so the deque maintenance is also O(n) amortized despite the while loop inside the for loop.
• Space: O(1) for scalar aggregates (sum, count). O(min(k, alphabet size)) for a frequency map bounded by the window, or O(k) for a monotonic deque, since it holds at most one index per window position.
• Contrast with the brute-force baseline of O(n·k) time (recompute each window from scratch) or O(n log k) if you naively used a heap per window without evicting stale entries correctly.

Pitfalls and interview gotchas

• Off-by-one on window boundaries. Decide up front whether you index by right - k + 1 or maintain an explicit left variable that you increment every time right - left + 1 == k; the latter is easier to get right if you're not used to the arithmetic.
• k > len(arr). Always guard for this — either return early or let your loop bounds naturally produce zero valid windows; don't let it silently index out of bounds.
• Forgetting to remove the outgoing element. This is the bug that turns your "sliding" window into a "growing" window and quietly produces wrong answers only once right >= k, which can slip past small test cases.
• Recomputing instead of updating. If you find yourself scanning all k elements inside the loop to get the current window's sum/count, you've written O(n·k), not O(n) — the entire point of this pattern is the incremental update.
• Floating point on averages. Track the integer running sum and only divide once at the end (or when comparing), rather than dividing on every step, to avoid unnecessary floating-point drift.
• Frequency-map equality checks. When comparing two fixed-size frequency maps (e.g., "does this window's letter counts match the target's?"), don't do an O(alphabet) comparison at every step if you can avoid it — maintain a running "number of characters currently matching" counter instead, updated only when a specific character's count crosses into or out of equality. This turns an O(n · alphabet) solution into O(n).

Fixed-size vs. variable-size at a glance

	Fixed-size	Variable-size
Window length	Given (k), constant throughout	Unknown; itself the answer
Loop shape	Single for, conditional shrink	for (expand) + inner while (shrink)
Typical ask	"max/min/count over every window of size k"	"longest/shortest subarray satisfying condition"
When left moves	Every step once window is full, by exactly one	Zero or more times per step, until valid again

A worked pattern (not one of your assigned problems)

To internalize the template without spoiling any problem below, trace it on a made-up task: given an array of temperatures, find the maximum 3-day rolling average.

Notice the initial window is seeded with a direct sum over the first k elements (an O(k) one-time cost), and every step after that is a single addition and subtraction — the incremental update that makes the whole pass O(n).

Where this connects

This is a special case of the same-direction two-pointer reasoning from the Two Pointers topic, and the monotonic-deque variant is your first taste of the Monotonic Stack topic that comes right after this one. Once you're comfortable sliding a window of known size, the natural next question — "what if I don't know the size and have to discover it?" — is exactly what Variable-Size Sliding Window answers next.