Sliding WindowAlgorithmaka fixed-length window, k-window, rolling computation

Sliding Window (Fixed Size)

Maintain an aggregate over every length-k contiguous subarray by adding the entering element and removing the leaving one, turning O(n·k) into O(n).

▶ VisualizePattern: Sliding WindowPractice (3)
Progress

Overview

A fixed-size sliding window answers questions of the form "for every contiguous block of exactly k elements, compute some aggregate" — the maximum sum, the average, the number of distinct values, whether a pattern matches. The naive approach recomputes the aggregate from scratch for each of the n − k + 1 positions, costing O(n·k). The window trick observes that consecutive blocks differ by exactly two elements: one enters on the right, one leaves on the left. If the aggregate can be updated under a single insertion and a single deletion in O(1) (or O(log k)), the whole scan costs O(n).

Sums, counts, and hash-map frequencies update trivially. Maximum and minimum do not — removing the current maximum requires knowing the next one — which is where a Monotonic Queue enters (Sliding Window Maximum). Hash-based string matching (Rabin–Karp) is a fixed window over characters with a rolling hash as the aggregate.

contiguoussubarraysize kO(n)rolling sum

Intuition

A mental model before the formal terms.

Picture a cardboard frame exactly k cells wide sliding along a strip of numbers. Each time you push the frame one cell right, one number appears on the right edge and one disappears on the left. To keep a running total you do not re-add all k numbers — you add the newcomer and subtract the departed. The frame never shrinks or grows, so there is no decision to make about its size, only a bookkeeping update.

How it works

  1. Build the first window: process a[0..k) into the aggregate (e.g. sum, or a frequency map).
  2. Record the answer for window position 0.
  3. For r from k to n − 1: add a[r] to the aggregate and remove a[r − k] from it. The window is now a[r−k+1..r].
  4. Update the answer (max/min/count/match) using the current aggregate.
  5. Return the answer after the last window. There are exactly n − k + 1 windows.

Why it works

Invariant: after processing index r, the aggregate exactly describes the multiset {a[r−k+1], …, a[r]}. It holds after the initial build. Each step adds a[r] and removes a[r−k]; the multiset of the new window is the old multiset plus a[r] minus a[r−k], so an aggregate that is a function of the multiset (sum, frequency counts, count of distinct values) is updated exactly.

Every window is visited once and every element enters once and leaves once, giving 2n aggregate updates. Correctness of the final answer follows because the set of windows examined is precisely all n − k + 1 contiguous length-k subarrays — nothing is skipped or double-counted.

The approach is only valid for aggregates that support deletion. Sum, product without zeros, frequency counts and XOR do; max/min need a Monotonic Queue or a balanced structure because deletion can change the answer to an element not currently tracked.

Recognition

How to tell a problem wants this.

  • The statement contains "contiguous", "subarray" or "substring" together with an explicit fixed length: "of size k", "of length k", "every k consecutive elements", "each window".
  • "Maximum average subarray of length k", "number of subarrays of size k with average ≥ threshold", "count vowels in every substring of length k".
  • String problems asking whether a pattern of length m appears as a permutation/anagram ("find all anagrams of p in s", "permutation in string") — the window has fixed width |p| and the aggregate is a frequency map; see Sliding Window with Frequency Map.
  • "Repeated DNA sequences of length 10" — a fixed window with a hash or a rolling encoding.
  • Constraints n ≤ 10^5 and k ≤ n with an obvious O(n·k) brute force that would time out.
“contiguous subarray” → Sliding Window

Interactive visualization

Play, step, change the input. ← → and space work too.

2
0
1
1
5
2
1
3
3
4
2
5
8
6
1
7
4
8
6
9
1/16Window size k=3. Sum the first window a[0..2] directly: 8. This is the only time we add k elements.
Current windowLeft the windowEnteringBest window
PseudocodeLearn Sliding Window (Fixed Size) →
1sum = a[0] + ... + a[k-1]; best = sum
2for r in k .. n-1:
3  sum += a[r] - a[r-k]
4  best = max(best, sum)
5return best
Variables
sum8
best8
k3
Complexity
best O(n)
avg O(n)
worst O(n)
space O(1)
Speed

Pseudocode

1window_sum = sum(a[0..k))
2best = window_sum
3for r in k..n-1:
4  window_sum += a[r] - a[r - k]   # newcomer in, oldest out
5  best = max(best, window_sum)
6return best

Implementations

1# Maximum Average Subarray I: largest average of any contiguous subarray of length k
2def find_max_average(a: list[int], k: int) -> float:
31 · Build the first window a[0..k)
4    window = sum(a[:k])
52 · The first window is the initial best
6    best = window
73 · Slide: add the entering element, remove the leaving one
8    for r in range(k, len(a)):
9        window += a[r] - a[r - k]
104 · Update the best window sum
11        best = max(best, window)
125 · Convert the best sum to an average
13    return best / k
Walkthrough
  1. sum(a[:k]) builds the first window; the slice copies k elements but that is a one-time O(k) cost.
  2. best = window records the first window before sliding.
  3. range(k, len(a)) iterates the right edge over every remaining window.
  4. window += a[r] - a[r - k] is the O(1) update; Python ints never overflow.
  5. best / k is true division and returns a float even for integer operands.
Complexity (this implementation)
time O(n) · space O(1)

The one-time a[:k] slice allocates O(k); use sum(itertools.islice(a, k)) to avoid the copy.

Language notes
  • itertools.islice(a, k) iterates the first k elements without slicing.
  • Because ints are arbitrary precision, there is no long long concern; the trade-off is that big-int arithmetic is slower than fixed-width.
  • / is float division; // is floor division — use / for an average.
Common mistakes in this language
  • Re-slicing sum(a[r - k + 1 : r + 1]) inside the loop — O(n·k).
  • Using // and truncating the average.
  • Off-by-one on the leaving element (a[r - k + 1]).
Language differences that matter here
  • Running-sum width: C++ needs long long (an int overflows around 2.1e9); JS/TS are exact to 2^53 in a double; Python ints are unbounded.
  • Averaging: C++ needs an explicit double cast to avoid integer division; Python / is always float division; JS/TS have only one numeric type.
  • Building the first window: Python sum(a[:k]) and JS slice().reduce() copy k elements; the C++ and TS loops (or std::accumulate) do not.

Complexity

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

O(k) or O(Σ) space if the aggregate is a frequency map; O(n) with a monotonic deque for max/min windows.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Every contiguous block of a known, fixed length must be evaluated.
  • The aggregate supports O(1) add and remove: sum, count, frequency table, XOR, product of non-zero values.
  • Streaming data where only the last k items matter (moving averages, rate limiting).
  • Fixed-length pattern matching over strings (anagram search, rolling hash).
Avoid it when
  • The window length is not fixed but determined by a condition ("longest substring with…", "smallest subarray whose sum ≥ s") — use Sliding Window (Variable Size).
  • Subarray is not required to be contiguous ("subsequence") — sliding windows only cover contiguous ranges; think Dynamic Programming or sorting.
  • The aggregate does not support removal in O(1) (max, min, median) — add a Monotonic Queue, two heaps, or a balanced BST; or, for range queries with no updates, precompute a Sparse Table.
  • You need sums of *arbitrary* ranges, not sliding ones — Prefix Sum answers any [l, r] in O(1) after O(n) preprocessing.

Alternatives

Prefix SumSliding Window (Variable Size)Monotonic QueueSparse Table

Common mistakes

  • Removing a[r − k + 1] instead of a[r − k] — off by one on which element leaves.
  • Not handling k > n (no window exists) or k == 0.
  • Recomputing the aggregate inside the loop, silently reverting to O(n·k).
  • Integer overflow of the running sum in fixed-width languages when k · max(a) exceeds 2^31.
  • Using a fixed window for a problem whose constraint ("at most k distinct") actually defines a variable window.

Interview patterns

  • Maximum Average Subarray / maximum sum of k consecutive elements.
  • Find All Anagrams in a String and Permutation in String — fixed window of width |p| plus a frequency map.
  • Sliding Window Maximum — fixed window plus a Monotonic Queue to support removal of the max.
  • Repeated DNA Sequences — window of 10 with a hash set (or 2-bit rolling encoding).
  • Number of Sub-arrays of Size K and Average ≥ Threshold; Grumpy Bookstore Owner (best window to "flip").
  • Rabin–Karp: rolling hash is a fixed window whose aggregate is a polynomial hash.
Interview questions on this
Mock interviews

Example problems

Repeated DNA SequencesmediumPermutation in StringmediumSliding Window Maximumhard