Fixed-size window

34 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Given 1, 12, −5, −6, 50, 3, find the four consecutive numbers with the largest average. By hand: add 1 + 12 − 5 − 6 = 2, then 12 − 5 − 6 + 50 = 51, then −5 − 6 + 50 + 3 = 42. The best is 51, so the average is 12.75.

Each of those sums took four additions. With n numbers and windows of size k there are n − k + 1 windows and each costs k additions: O(n · k). For a million numbers and windows of 10,000 that is ten billion additions. Look at what was wasted: the second sum re-added 12, −5 and −6, which were already in the first sum.

Build the structure, one piece at a time

The window is just two things: a range of exactly k positions, and a running aggregate of what is inside it. The aggregate here is a sum, but it can be a count table, a set, or anything you can update by adding one element and removing one.

Piece one: build the first window honestly, adding its k elements. Sum = 2 for positions 0 … 3.

Piece two: slide. To move the window one step right, add the element that enters on the right and subtract the element that leaves on the left. Two operations, whatever k is.

For "does this window contain a permutation of a pattern", the aggregate is a 26-entry letter count: entering a letter adds one to its count, leaving subtracts one, and the window matches when the counts equal the pattern's counts. For "any duplicate within distance k", the aggregate is a set of the last k elements.

Why it is correct

The invariant: after the window has moved to end at position r, the aggregate describes exactly positions r − k + 1 … r. It holds for the first window by construction. A slide adds position r + 1 and removes position r − k + 1, so the described set becomes r − k + 2 … r + 1, which is exactly the next window. For sums this is the identity

sum[r−k+2 … r+1] = sum[r−k+1 … r] + nums[r+1] − nums[r−k+1]

and for a count table it is the same statement per value. Since every window of size k is visited and each one's aggregate is exact, the maximum (or the first match) found is the true answer.

Why it is fast

Building the first window costs k; each of the n − k slides costs 2. Total about k + 2(n − k) < 2n, which is O(n), independent of k. The million-number example drops from ten billion additions to about two million. The whole saving is that an element is added once and subtracted once instead of being re-added in every window it belongs to.

How to recognise it in an interview

Cues: "of length k", "every window of size k", "consecutive k elements", "within distance k", "substring of the same length as the pattern". When the size is fixed, the window never needs a shrink loop; it is exactly add-one, drop-one.

Say: "I will keep a running aggregate of exactly k elements and slide it by adding the new right element and removing the old left one." Maximum Average Subarray I is the example. Permutation in String and Find All Anagrams in a String use a letter-count aggregate with the window size equal to the pattern's length. Contains Duplicate II uses a set of the last k elements and reports a hit when the entering element is already present.

02The idea in one line

Slide a width-k window: add the new right, drop the old left.

Reach for it when: Max average, anagram detection, k-length statistics.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Max average of size 4 in [1,12,-5,-6,50,3]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Keep a running sum of exactly k elements: add the new right, drop the old left
2. The window is a bracket of k cells; its sum lives in the state panel
3. First window [0..3]: sum = 2
4. Slide: + 50 − 1 → sum = 51
5. 51 beats the best so far: best = 51
6. Slide: + 3 − 12 → sum = 42
7. Best window [1..4] averages 12.75
8. Each element enters once and leaves once: O(n)

04Asked at Google

8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Sliding Window: Longest valid window, Shortest satisfying window, Count windows via at-most(k) trick, Window with a need-counter.