Sliding Window

On this page

The Idea
Build It
Know It
Break It
Use It

Quick reference

Fixed-size window	O(n)
Variable-size window	O(n) amortized
Recomputing every subarray from scratch (for comparison)	O(n²) or worse

The Idea

A window is just a contiguous stretch of the array — a start edge and an end edge, with everything between them "in the window." The brute-force way to answer a question like "what's the best sum of any 5 consecutive elements" is to check every possible stretch from scratch: for each starting point, walk forward and re-add every element in that stretch. That recomputes the same elements over and over. Sliding window instead keeps one window alive and slides it — as the end edge moves forward to include a new element, the start edge moves forward to drop an old one, and a running total is updated incrementally instead of rebuilt.

There are two shapes this takes. A fixed-size window always covers exactly k elements — it slides one step at a time, gaining one element on the right and losing exactly one on the left. A variable-size window grows and shrinks based on a condition: keep expanding the right edge while things are valid, and the moment they stop being valid, shrink from the left until they're valid again.

The upgrade sliding window makes: stop recomputing every subarray's total from scratch (O(n) work per subarray, O(n²) or worse overall) and instead update a running aggregate by exactly one element's worth of work as the window moves.

Build It

Window shapes

// Fixed-size window of width k
windowSum = sum of the first k elements
for right from k to length - 1:
    windowSum += arr[right]           // element entering on the right
    windowSum -= arr[right - k]        // element leaving on the left
    ... use windowSum ...

// Variable-size window
left = 0
for right from 0 to length - 1:
    ... add arr[right] to the window's running state ...
    while window is invalid:
        ... remove arr[left] from the window's running state ...
        left += 1
    ... window [left, right] is now valid — use it ...

fixed-size window — maintain a running aggregate

function maxFixedWindowSum(arr, k):
    windowSum = 0
    for i from 0 to k - 1:
        windowSum += arr[i]           // build the first window directly
    best = windowSum
    for right from k to length(arr) - 1:
        windowSum += arr[right]         // the element sliding in
        windowSum -= arr[right - k]      // the element sliding out
        best = max(best, windowSum)
    return best

variable-size window — grow, then shrink until valid again

function smallestWindowAtLeastTarget(arr, target):
    left = 0
    windowSum = 0
    best = infinity
    for right from 0 to length(arr) - 1:
        windowSum += arr[right]                 // grow: always add the new right edge
        while windowSum >= target:                // shrink while still valid
            best = min(best, right - left + 1)
            windowSum -= arr[left]
            left += 1
    return best if best != infinity else 0

The right edge only ever moves forward, and the left edge only ever moves forward — neither one ever backtracks. That's what keeps this a single pass instead of a nested re-scan.

Know It

The nested while-inside-for shape looks like it could be O(n²), but it never re-examines an element it has already dropped. Every index enters the window exactly once (when right reaches it) and leaves exactly once (when left passes it) — total movement across both edges is at most 2n steps.

Operation	Time	Space	Why
Fixed-size window	O(n)	O(1) extra (plus whatever the window's tracked state needs)	One slide per position: one element added, one removed, both O(1) — n slides total.
Variable-size window	O(n) amortized	O(1) extra (plus tracked state)	Recall "amortized" from Arrays & Strings Fundamentals: the inner while-loop looks like it could repeat, but left only ever moves forward and can advance at most n times total across the entire run — so the two nested loops together still add up to O(n), not O(n²).
Recomputing every subarray from scratch (for comparison)	O(n²) or worse	O(1)	Re-summing a stretch of up to n elements for each of up to n starting points is the cost sliding window exists to avoid.

Break It

Window larger than the array

k exceeds the array's length

A fixed-size window of width k assumes at least k elements exist. Building "the first window" by summing arr[0..k-1] without checking length first reads past the end of the array — always validate k against the array's length before the first window is built.

Recomputing the aggregate instead of updating it

each slide re-sums the whole window instead of adjusting by one element

It's easy to write code that looks like sliding window (a loop with a window of size k) but re-sums all k elements at every position instead of adding the entering element and subtracting the leaving one. That silently turns an O(n) sliding window into an O(n·k) brute force — same structure, none of the speedup.

Off-by-one on window boundary indices

computing the window's width or its leaving-element index

The element leaving a fixed-size window at position right is at right - k, not right - k + 1 or right - k - 1 — and a window's width is right - left + 1, not right - left. Both are easy to get backward, and both fail silently (wrong answer, not a crash) rather than loudly.

A shrink condition that never triggers

the while-loop's validity check is written so it's always true (or always false)

If the shrink condition can never become false, left never advances and the window only grows — turning a variable-size window into a full O(n) rescan on every step (O(n²) overall) instead of an amortized O(n) sweep. Trace the condition against a small example by hand before trusting it.

Use It

Maximum Subarray

Extend the running-aggregate idea from Build It: keep a running sum that resets to zero (starts a fresh window) whenever it goes negative, since a negative running sum can only drag down everything that comes after it. Track the best sum seen at any point.

Medium

Maximum Average Subarray I

The textbook fixed-size window: compute the first window's sum directly, then slide one step at a time by adding the entering element and subtracting the leaving one — never re-sum the whole window.

Easy

Longest Substring Without Repeating Characters

Variable-size window: grow the right edge while every character inside stays unique, tracked with an array indexed by character code (the same addressable-slots idea from Arrays & Strings Fundamentals). The moment a repeat shows up, shrink from the left until it's gone.

Medium

Minimum Size Subarray Sum

The smallestWindowAtLeastTarget shape from Build It, almost verbatim: grow the right edge adding to a running sum, and the moment the sum meets the target, shrink from the left as far as possible while it still does — tracking the smallest width seen.

Medium

Longest Repeating Character Replacement

Track a frequency count (an array indexed by letter) for the characters currently in the window, plus the count of whichever letter is most frequent inside it. The window stays valid as long as (window size − that peak count) is at most k replacements; shrink from the left when it isn't.

Medium

Permutation in String

Fixed-size window sized to the pattern's length: keep a running frequency count (array indexed by letter) of the window's letters, and compare it against the pattern's frequency count each slide — one array comparison per shift instead of resorting or rebuilding.

Medium

Find All Anagrams in a String

The same fixed-size frequency-matching window as Permutation in String — don't stop at the first match, slide all the way through and record every starting index where the window's letter counts match the pattern's.

Medium

Fruit Into Baskets

A variable-size window that's allowed at most two distinct fruit types: grow the right edge always, track a count of each type currently inside, and shrink from the left whenever a third type would otherwise have to be added.

Medium

Contains Duplicate II

A fixed-size window of width k: keep a quick lookup of which values are currently inside the window (you'll meet the fast structure purpose-built for this next topic). If the value about to enter is already in that lookup, you've found your answer — otherwise drop the oldest value out of the lookup as it exits the window.

Easy

Maximum Number of Vowels in a Substring of Given Length

A textbook fixed window again: count vowels in the first window of size k directly, then slide — add one if the entering character is a vowel, subtract one if the leaving character was one — tracking the max seen.

Medium