Two Pointers & Windows

Sliding Window (Fixed Size)

Maintain an aggregate over every window of size k by adding the new element and removing the old one.

Medium, about 60 minutes to practise.

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

LR
2
1
5
1
3
01234
L → index 0R → index 2

First window sum = 2+1+5 = 8. best = 8. Do not skip evaluating it.

window = sum(a[:k]); best = window

Live template

Line 1 active

1window = sum(a[:k]); best = window
2for i in range(k, len(a)):
3 window += a[i] - a[i - k]
4 best = max(best, window)

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.

  1. window = sum(a[:4]) = 2, best = 2.
  2. i=4: add 50, remove 1 → window 51, best 51.
  3. i=5: add 3, remove 12 → window 42, best stays 51.
  4. Answer is 51/4.

In code:

  • window = sum(a[:k]); best = window
  • for 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.

All lessons