The sliding window mental model

Memorising algorithms does not scale. There are too many, and the ones you memorise are never quite the ones you are asked about.

What does scale is recognition — a small set of signals that tell you which shape of solution the problem wants, before you have worked out any of the details. Sliding window is one of the most reliably recognisable of these, which makes it a good one to learn properly.

The idea

You have a sequence, and you care about some contiguous run inside it. Rather than examining every possible run from scratch, you keep a window over part of the sequence and move it along, updating your answer as you go.

The window advances one position at a time. At each stop you ask whether what is inside it beats the best you have seen, keep the answer if so, and carry on to the end.

The saving comes from not recomputing. When the window moves right by one, exactly one element enters and one leaves. If you are tracking a sum, that is one addition and one subtraction — not a fresh pass over the whole window.

Two variants

Fixed size. The window is always K wide. Both edges move together. Use this when the problem hands you the size: maximum sum of a subarray of size K.

Dynamic size. The window grows and shrinks, like a caterpillar. The right edge advances to expand; the left edge advances to contract when some condition is violated.

Use this when the problem gives you a condition instead of a size: shortest subarray with sum at least S, longest substring with at most K distinct characters.

Choosing between them is not a judgement call. The problem tells you which one it is by whether it specifies a width or a constraint.

Why it beats the obvious approach

The brute-force version fixes a starting index and extends from it, then moves the start and does it again. Every element gets visited once per window it belongs to, so the same values get re-added over and over.

That costs $O(N \times K)$ — $N$ starting positions, up to $K$ work at each. When the window size grows with the input, $K$ approaches $N$ and you are at $O(N^2)$.

The sliding window is $O(N)$. Each element enters the window exactly once and leaves exactly once, so the total work is bounded by twice the length regardless of how wide the window gets.

That last sentence is also the proof that the dynamic variant is linear, which surprises people the first time: it has a nested loop, but the inner loop's total iterations across the whole run cannot exceed $N$, because each element can only be removed once.

How to spot one

Three signals, and you usually get all three at once.

The data is sequential and the answer is contiguous. Arrays, strings, linked lists. The words substring and subarray are the giveaway — they mean adjacent elements, which is exactly what a window covers. If the problem would accept a subsequence with gaps, this is not a window problem.

The question asks for an extremum or a check. Longest, shortest, maximum, minimum, contains. Something to maximise or minimise over the candidate windows.

There is a constraint that defines validity. A fixed size, a sum threshold, a limit on distinct characters. This is what tells the left edge when to move.

Once you have all three, the implementation is mechanical: decide what state to track, decide when to shrink, and decide when to record the answer.

Fixed-size, in code

Maximum sum of a subarray of size K:

func maxSumSubarray(arr []int, k int) int {
	if len(arr) < k {
		return 0
	}
 
	windowSum := 0
	for i := 0; i < k; i++ {
		windowSum += arr[i]
	}
 
	maxSum := windowSum
	for i := k; i < len(arr); i++ {
		windowSum += arr[i] - arr[i-k]
		maxSum = max(maxSum, windowSum)
	}
	return maxSum
}

The highlighted line is the technique in its entirety: add what entered, subtract what left. Everything else is bookkeeping.

Dynamic-size, in code

Shortest subarray with a sum of at least s:

func minSubarrayLength(arr []int, s int) int {
	minLength := math.MaxInt
	windowSum, windowStart := 0, 0
 
	for windowEnd := 0; windowEnd < len(arr); windowEnd++ {
		windowSum += arr[windowEnd]
 
		for windowSum >= s {
			minLength = min(minLength, windowEnd-windowStart+1)
			windowSum -= arr[windowStart]
			windowStart++
		}
	}
 
	if minLength == math.MaxInt {
		return 0
	}
	return minLength
}

The outer loop grows the window; the inner loop shrinks it while the condition still holds. The inner loop is what makes this dynamic, and — as above — it does not make it quadratic.

When you need extra state

The hardest variant adds a data structure. Longest substring with at most K distinct characters cannot be tracked with a running sum — you need a map from character to count, and the shrink condition becomes "while the map has more than K entries".

The shape is unchanged. Grow on the right, shrink on the left, record the best. Only what you are tracking has changed, from a number to a map.

That is worth holding on to, because it is what makes this a mental model rather than an algorithm. The window mechanics stay fixed across every problem in the family. What varies is the state you carry and the condition that moves the left edge — and once you see a problem in those terms, writing it is the easy part.