Sliding Window

Solve subarray and substring problems in one pass by keeping a window of contiguous elements and updating it as it moves, instead of recomputing every range.

Overview

The idea

A window is a contiguous range of an array or string, marked by two indexes, left and right. Many problems ask about every contiguous range: the largest sum, the longest run with no repeats, the number of ranges that meet a rule. Checking each range from scratch repeats work, because neighboring ranges share almost all of their elements.

The sliding window keeps a small summary of the current range (a sum, a count map, a set) and updates it when one element enters on the right or one leaves on the left. Each update costs O(1), so the whole scan costs O(n).

Recompute each window of size k — about 99 million additions — O(n·k)
Slide: add the new element, drop the old one — about 199 thousand operations — O(n)

The numbers come from (n − k + 1) · k = 99,001,000 and k + 2(n − k) = 199,000.

Fixed-size window

When the problem gives the window size k, build the first window, then move it one step at a time. Each step adds nums[i] and subtracts nums[i - k].

A trace on [2, 5, 1, 8, 3, 7, 4] with k = 3, looking for the largest sum:

start — 2, 5, 1 — none — [2, 5, 1] — 8 — 8
3 — 8 — 2 — [5, 1, 8] — 14 — 14
4 — 3 — 5 — [1, 8, 3] — 12 — 14
5 — 7 — 1 — [8, 3, 7] — 18 — 18
6 — 4 — 8 — [3, 7, 4] — 14 — 18

The answer is 18, and each element was added once and subtracted at most once.

Variable-size window

When the size is not given, the window grows and shrinks. The right edge moves forward on every step and adds one element. The left edge moves forward only when the window breaks the rule (for longest-window problems) or while it still meets the rule (for shortest-window problems).

A trace of the longest substring without a repeated character in abcabcbb. The state is a count of each character in the window; the rule breaks when the new character's count reaches 2.

0 — a — none — 0 — a — 1
1 — b — none — 0 — ab — 2
2 — c — none — 0 — abc — 3
3 — a — a — 1 — bca — 3
4 — b — b — 2 — cab — 3
5 — c — c — 3 — abc — 3
6 — b — a, b — 5 — cb — 3
7 — b — c, b — 7 — b — 3

The inner loop sometimes removes two characters, yet left moves at most n times in total. That is why the nested loop is still O(n): the work is counted per element, not per step.

Longest versus shortest

The two variable templates differ in when they shrink and when they record the answer.

Longest valid window — the window is invalid — after shrinking, when the window is valid — Longest Substring Without Repeating Characters
Shortest valid window — the window is still valid — inside the loop, before each removal — Minimum Size Subarray Sum
Count valid windows — the window is invalid — add right - left + 1 after shrinking — Subarray Product Less Than K

A trace of the shortest subarray with sum at least 7 in [2, 3, 1, 2, 4, 3]:

0 to 2 — 2, 3, 1 — none, the sum stays below 7 — none
3 — 2 — [2, 3, 1, 2] sum 8 — 4
4 — 4 — [3, 1, 2, 4] sum 10, then [1, 2, 4] sum 7 — 3
5 — 3 — [2, 4, 3] sum 9, then [4, 3] sum 7 — 2

When shrinking is safe

The left edge never moves back, so the template is correct only when the rule is monotone. For longest problems, every window inside a valid window must also be valid. For shortest problems, every window that contains a valid window must also be valid. With non-negative numbers the second rule holds: adding an element never lowers the sum. With negative numbers it fails.

Take [-2, 3] and the target sum 3. The window [-2, 3] sums to 1, so the template never shrinks, and it misses [3], which meets the target.

Sums over non-negative numbers — yes — the variable window
At most K distinct values, no repeats, at most K of a character — yes, the rule only gets easier as the window shrinks — the variable window
At least K of every character in the window — no, shrinking can break it or fix it — fix the number of distinct characters (1 to 26) and run one window per count
Sums with negative numbers — no — prefix sums with a hash map (Subarray Sum Equals K), or prefix sums with a monotonic deque (Shortest Subarray with Sum at Least K)

> [!IMPORTANT] > Before you write a variable window, say out loud why shrinking is safe. This check is where most wrong solutions break.

Counting windows, and the exactly K trick

To count the subarrays that meet an at-most rule, run the longest-window template and, after each shrink, add right - left + 1: every subarray that ends at right and starts at or after left is valid.

An exactly K rule is not monotone, since shrinking can move the count from K to K − 1. Count it as the difference of two at-most counts.

For [1, 2, 1, 2, 3] and K = 2: at most 2 distinct gives 12 subarrays, at most 1 distinct gives 5, so exactly 2 distinct gives 7.

0 — 1 — 0 — [1] — 1
1 — 2 — 0 — [1, 2] — 2
2 — 1 — 0 — [1, 2, 1] — 3
3 — 2 — 0 — [1, 2, 1, 2] — 4
4 — 3 — 3 — [2, 3] — 2

The at most 2 total is 1 + 2 + 3 + 4 + 2 = 12.

The window maximum with a monotonic deque

A sum can be updated by subtraction, but a maximum cannot: when the largest element leaves, you need the next largest. A deque (a queue open at both ends) of indexes solves this. Keep the values in the deque decreasing from front to back:

Before adding index i, pop from the back every index whose value is at most nums[i]. Those elements are older and not larger, so they can never be a maximum again.
Push i on the back.
If the front index has left the window (it is at most i − k), pop it from the front.
The front is the window maximum.

A trace on [1, 3, -1, -3, 5, 3, 6, 7] with k = 3, showing values:

0 — 1 — none — 1 — none yet
1 — 3 — 1 — 3 — none yet
2 — -1 — none — 3, -1 — 3
3 — -3 — none — 3, -1, -3 — 3
4 — 5 — -3, -1, 3 — 5 — 5
5 — 3 — none — 5, 3 — 5
6 — 6 — 3, 5 — 6 — 6
7 — 7 — 6 — 7 — 7

Each index is pushed once and popped at most once, so the whole pass is O(n). Python's collections.deque appends and pops at either end in about O(1); a plain list pays O(n) for pop(0), so do not use one as the queue.

Choosing the state

The window is only as fast as its state. Pick the smallest summary that answers the question in O(1).

Sum or average — one running number — depends on the target
No repeated characters — count map, or last index of each character — every count is at most 1
At most K distinct values — count map, delete keys that reach 0 — the map has at most K keys
Is it an anagram of p — 26 counts and a matched-letters counter — all 26 counts match
Maximum or minimum — monotonic deque of indexes — always; read the front
Characters to replace to make all the same — count map and the highest count seen — length - highest count is at most K

What you will be able to do

Tell a fixed window from a variable one, and pick the longest, shortest or counting template.
Explain why the expand and shrink loop is O(n) even with a nested while.
Check that shrinking is safe, and switch to prefix sums when negative numbers break it.
Count exactly K windows as atMost(K) minus atMost(K − 1).
Keep a window maximum or minimum with a monotonic deque.

When to use it

The question is about contiguous subarrays or substrings, not any subset
A fixed size k is given: the largest sum, average or count over every k elements
Longest or shortest range that meets a rule, where the rule stays true as the range shrinks
Counting ranges with at most K of something (and exactly K, by subtracting two at-most counts)
Character or value counts inside a range: anagrams, distinct values, repeats
The maximum or minimum of every window of size k (monotonic deque)

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio