1Understand
The idea
For every window of size k, do not recompute the window from scratch: when it slides one step, add the element that enters and remove the one that leaves. Sums, counts and frequency maps all update in O(1), so all windows cost O(n) together.
Intuition
For every window of size k, do not recompute from scratch. When the window slides one step, add the element that enters and remove the one that leaves. Sums, averages and many frequency maps update in O(1) per step, so all windows together cost O(n).
Initialise the first window carefully, then loop from index k onward. If k exceeds the array length, handle that edge before sliding.
When the aggregate is "max in the window", a plain sum-style update is not enough, that needs a monotonic deque.
What you will be able to do
- Update the window in O(1)
- Handle k larger than the input
When to use it
- "Every subarray / substring of length k"
- Maximum or average over windows of size k
2See it
Walkthrough
Max sum of window size k
a = [2, 1, 5, 1, 3], k = 3, add incoming, subtract outgoing.
1 / 4
First window sum = 2+1+5 = 8. best = 8. Do not skip evaluating it.
Live template
Line 1 active
Complexity: time O(n), space O(1) to O(k)
Time O(n), space O(1) for sums (or O(σ) if you track a frequency map of the window). Re-summing each window is O(n·k) and fails large n. Fixed windows are simpler than variable ones: no while-shrink loop.
Read the walkthrough as text
Maximum average subarray of length k. a = [1, 12, -5, -6, 50, 3], k = 4.
window = sum(a[:4]) = 2,best = 2.- i=4: add
50, remove1→ window51, best51. - i=5: add
3, remove12→ window42, best stays51. - Answer is
51/4.
In code:
window = sum(a[:k]); best = windowfor i in range(k, len(a)):window += a[i] - a[i - k]best = max(best, window)
3Recognise it
Kinds of problems (6)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Sum or average of each window
Example. Maximum average subarray of length k.
How. Window sum for first k; slide by += a[i], a[i−k] each step.
Count windows meeting a condition
Example. How many length-k subarrays have sum ≤ threshold.
How. Maintain window aggregate; after each slide, increment count if valid.
Anagram / permutation in a string
Example. Substring of s that is a permutation of p.
How. Fixed window length |p|; compare frequency arrays when the window is full.
Distinct elements per window
Example. Count different integers in each window of size k.
How. Freq map for current window; add on enter, remove on leave, read len(map).
Complement window (take from both ends)
Example. Max score removing k cards from ends of a row.
How. Fix left take count; right take is k−left; window sum is total, ends removed.
Circular input by doubling
Example. Best sum of k consecutive on a circular array.
How. Concatenate array with itself; run length-k windows on length 2n without wrapping logic.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Recomputing the window
Why it happens. Resumming each window is the first code that works on samples.
How it fails. k = 10⁴, n = 10⁵: inner sum per window is O(k) → O(n·k) TLE.
Fix. Slide: add incoming, subtract outgoing element at i−k in O(1).
First window skipped
Why it happens. The loop starts at index k and never scores indices 0..k−1 together.
How it fails. Maximum sum window of size 3 on [4,1,2], you never evaluate sum 4+1+2 = 7.
Fix. Build the first window before the loop; compare best, then slide from i = k onward.
Wrong outgoing element
Why it happens. Off-by-one when removing the element that left the window.
How it fails. At i = 5, k = 3, you subtract a[i−k+1] instead of a[i−k], window keeps stale values.
Fix. When window ends at i, outgoing index is always i, k (the element that just dropped off the left).
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.