The sliding window mental model

The term "mental model" is doing a lot of work in that title, and it is worth being precise about what it means here.

The goal is not to memorise specific algorithms or solutions. Memorising does not scale — there are too many algorithms, and the ones you memorise are never quite the ones you are asked about. What we are building instead is a method for recognising a broad class of problems that share a shape, whether they show up in an interview, in an application, or in a piece of production code. We want to internalise the model at a level abstract enough that it transfers, rather than learning any one problem by heart.

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.

At its core, the technique involves picturing two shapes. The first is a rectangle, standing in for whatever data structure you have — an array, a string, a linked list. It holds a sequence of elements that sit next to each other. Over some part of that rectangle you place a window. You then ask an optimisation question of whatever is inside the window: is this the best arrangement so far? You record the result, shift the window along, and ask again. Whenever the current window beats everything seen before, you store that value as your running best. You continue until the window reaches the end of the structure, which is your stopping point, and then return the stored value.

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. That description is specifically the fixed-size sliding window.

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 in lockstep. Use this when the problem hands you the size: maximum sum of a subarray of size K.

Dynamic size. The second approach is the dynamically resizing window, and it works rather differently. Instead of a fixed width, the window grows and shrinks as needed — much like a caterpillar moving along a branch, extending its front and then drawing up its back. The right edge advances to expand the window; the left edge advances to contract it when some condition is violated. There is considerably more flexibility in the size, and you keep going until you reach the end of the sequence, which again is the stopping point.

Use the dynamic variant 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.

It is not a matter of picking a favourite between the two. Different questions call for different solutions, and the nature of the problem tells you which technique applies. Choosing between them is not really a judgement call at all — the problem announces which one it is by whether it specifies a width or a constraint.

Why it beats the obvious approach

It is worth being clear about what we are improving on. The usual first attempt is the brute-force approach: fix a starting index, then walk forward through every combination that satisfies the criteria; then move the start along and do it again. Each iteration considers a different starting point and a different range of elements.

The problem is duplicated work. As you iterate, you keep revisiting values you have already processed, re-adding the same numbers in overlapping ranges. 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 removes the redundancy and gives you a linear algorithm. Each element enters the window exactly once and leaves exactly once, so the total work is bounded by twice the length of the sequence regardless of how wide the window gets. Rather than duplicating effort, you move along the array adding and subtracting values at the edges, never halting the traversal and never re-evaluating something you have already accounted for.

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. These problems suit anything you can traverse step by step, one element at a time, where what you care about is an uninterrupted run of adjacent elements. That run might sit in the middle of the structure or at either end, but it is always a contiguous subset. Arrays, strings, and linked lists all qualify — a linked list is not stored contiguously in memory, but you can still traverse it sequentially, which is what matters here.

• Items you can traverse one by one.
  • A continuous sequence of elements.
  • Strings, arrays of numbers or characters, linked lists, and so on.

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. The criteria that show up are consistently of one kind: find the smallest or largest element, identify the longest or shortest run, or determine whether something is present within a string or array. Minimums, maximums, lengths, containment. Running averages fall into the same family. The common thread is that you will need to calculate and track some value as the window moves.

• Minimum, maximum, longest, shortest, contained.
  • There is usually something to compute and carry.

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.

Three shapes you will actually meet

Beyond the two variants, it helps to recognise three concrete forms these problems take.

1. Fixed length

Maximum sum of a subarray of size K.

Here we have a constant window width and a value to maximise. This aligns directly with the fixed-size technique.

Input Array: [a, b, c, d, e, f, g, h, i, j]
 
Window of Size K = 3:
[a, b, c] => Sum = a + b + c
 
Sliding Window Approach:
  [a, b, c] d, e, f, g, h, i, j
   a, [b, c, d] e, f, g, h, i, j
   a, b, [c, d, e] f, g, h, i, j
   ...
 
Maximum Sum of Subarray = Max(a + b + c, b + c + d, c + d + e, ...)

2. Dynamic variant

Smallest sum greater than or equal to a value S.

The window is no longer a fixed K; it expands and contracts. Here we are looking for the smallest sum that still satisfies the condition of being at least S — pinpointing the window that comes as close as possible to S without falling under it.

Input Array: [p, q, r, s, t, u, v, w, x, y, z]
 
Window Size >= S:
[p, q, r, s, t, u, v] w, x, y, z
 
Moving Window to Find the Smallest Sum >= S:
[p, q, r, s] t, u, v, w, x, y, z
p, [q, r, s, t] u, v, w, x, y, z
...
 
Smallest Sum >= S is the Answer.

3. Dynamic variant with an auxiliary data structure

Longest substring with at most K distinct characters. String permutations.

This shares the dynamic shape but introduces an auxiliary structure — a hash map, a hash set, or an extra array, rather than a single variable or boolean flag. This is where the problems get genuinely interesting.

For the longest-substring case, you are examining sequential data under the constraint of at most K distinct characters. Because distinctness is the constraint, a map or set becomes necessary to track which characters are in the window and how many times each appears.

The permutation case is similar in shape: given a long input string and a shorter one, determine whether the shorter string appears as a permutation somewhere inside the longer.

Input String: "abcaabcde"
 
Using Sliding Window and Auxiliary Data Structure:
[a, b, c, a] a, b, c, d, e
    [a, b, c, a, a] b, c, d, e
    a, [b, c, a, a, b] c, d, e
    ...
 
Longest Substring with at Most K Distinct Characters = "bcaabc"

What they have in common

More important than any individual shape is what all of these questions share, because that is what the mental model is actually made of.

The first commonality is that everything is arranged in a sequence. Keywords such as substring and subarray signal sequential groupings directly, and they are reliable indicators that a window is the right tool.

The second is that each question specifies some sequential criterion — longest, smallest, contains, and so on. In the permutation case the criterion is whether a particular set of characters exists. Whether you are maximising or minimising, the presence of such a criterion is an unmistakable marker of this family of problems.

So the thing to hold on to is this: identify one or two criterion points and build the window around them. Maximise the sum with the width fixed at K. Minimise the sum subject to it being at least S. Maximise the length of a substring subject to at most K distinct characters. Determine whether one string exists as a permutation inside another. These recurring themes are the foundation of the technique.

Fixed-size, in code

Maximum sum of a subarray of size K:

package main
 
import "fmt"
 
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
}
 
func main() {
	arr := []int{2, 1, 5, 1, 3, 2, 9, 7}
	fmt.Println("Maximum sum:", maxSumSubarray(arr, 3))
}

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:

package main
 
import (
	"fmt"
	"math"
)
 
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
}
 
func main() {
	arr := []int{2, 1, 5, 2, 3, 2}
	fmt.Println("Minimum length:", minSubarrayLength(arr, 7))
}

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 established 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.

Conclusion

The sliding window is a versatile strategy for optimising over contiguous runs of data. By moving a window across the sequence and evaluating each subset as it goes, you can find the best answer available in an array, string, or linked list in a single linear traversal, without ever re-examining a value you have already accounted for.

Its real value, though, is not the technique itself but the recognition. Once you can look at a question and see sequential data, an extremum, a validity constraint, you already know the shape of the answer before you have written a line — and that recognition transfers to problems you have never seen, which is the entire point of building a mental model rather than memorising solutions.