Sliding Window: The Art of the Moving Frame · Data Structures & Algorithms

Say you want the largest sum of any k consecutive numbers in an array. The obvious loop sums each window from scratch, which means every window re-adds the k-1 elements it already shared with the one before it. Sliding window refuses to repeat that work. You hold a single window that expands on the right and contracts on the left as you scan, so one element enters and one leaves per step. The O(n²) scan drops to O(n).

Two shapes cover almost everything you'll run into. Fixed-size windows always span exactly k elements, the kind you get from "max sum of k elements." Variable-size windows grow and shrink against a constraint, like "a [[prem:/guides/foundations/sliding-window/longest-substring-without-repeating|question]]," where the right size isn't knowable until you find it. The sliding itself is never the hard part; recognizing which shape you're staring at is.

The Core Idea

Picture a frame laid over the array that exposes exactly k elements. Slide it one step right and the mechanics are fixed: the leftmost element falls out, a new one joins on the right, and everything in the middle stays exactly where it was. That overlap in the middle is the entire reason the technique buys you anything.

Window at Position 0

Our window covers the first 3 elements. Sum = 2+1+5 = 8.

Window sum = 8

Four windows, and we paid for four adds and four subtracts instead of 4×3=12 element accesses. Scale it up and the gap turns absurd. With k=1000 and n=1,000,000, brute force reads k elements for each of n-k+1 windows, roughly 1 billion operations. Sliding window does one add and one remove per step, so about 2 million total. That 500x gap is the line between an accepted solution and a timeout.

Why This Works

Incremental change is the whole trick. Slide the window one position and the update stays trivial:

New Window = Old Window - (element leaving) + (element entering). This works for sums, counts, frequencies, and many other aggregate properties. The window state can be maintained with O(1) work per slide.

A problem that looks like it demands examining every subarray collapses into one pass, carrying the window state forward as you move.

The Complexity Win

The difference is easiest to see side by side. Brute force examines every window from scratch; the sliding window carries its state forward:

O(n×k) Brute Force. Recompute every window.
O(n) Sliding Window. Maintain state incrementally.
999M Saved Ops. K=1000, n=1,000,000.
1000x Speedup. At typical interview scale.

The mental trigger: When you see "contiguous subarray" or "substring" combined with "find maximum/minimum/count," reach for sliding window. The contiguous constraint is what makes the incremental update possible.

The Two Flavors

These problems come in two varieties. Telling them apart is most of the work:

Fixed-Size Window

Window size is given

The window size k is specified in the problem. You slide it across, updating your result at each position. Classic example: "maximum sum subarray of size k."

Max Sum Subarray of Size KMaximum of All Subarrays (Sliding Maximum)A [[prem:/guides/foundations/sliding-window/find-all-anagrams|question]]

Variable-Size Window

Window size depends on a condition

The window expands until some condition is violated, then shrinks until it's valid again. You're finding the longest/shortest window that satisfies a constraint.

A [[prem:/guides/foundations/sliding-window/longest-substring-without-repeating|question]] CharactersA [[prem:/guides/foundations/sliding-window/minimum-window-substring|question]]

Fixed-size is the gentler of the two, since the window never changes size and you always know how much you're holding. Variable-size asks more of you, because now you decide when to expand and when to shrink. Both get full treatment ahead.

Spotting Sliding Window Problems

A few phrases in the problem statement give it away:

"Contiguous subarray" or "substring"

→ Sliding Window

Contiguous means adjacent elements, perfect for a sliding frame.

"Of size k" or "of length k"

→ Fixed-Size Window

Size is given upfront. Classic sliding window setup.

"Longest/shortest that satisfies..."

→ Variable-Size Window

You're searching for optimal window size, not given one.

"At most k distinct" or "sum ≤ target"

→ Variable-Size + Shrinking

Constraint can be violated, so shrink the window until valid.

The Template

Most sliding window solutions share one skeleton. You fill in the specifics per problem:

python

def sliding_window(arr, ...):
    left = 0
    window_state = ...  # sum, count, hash map, etc.
    result = ...        # what we're tracking
    
    for right in range(len(arr)):
        update_window(arr[right])       # EXPAND: add right element
        
        while window_is_invalid():     # SHRINK: remove from left
            remove_from_window(arr[left])
            left += 1
        
        result = update_result(result)  # UPDATE: record result
    
    return result

The structure is always: expand → shrink (if needed) → update. What changes between problems is how you maintain window state and what makes a window "valid."

That nested while inside the for looks like it sneaks O(n²) back in. It doesn't. The left pointer only moves forward, never back, so across the whole run it advances at most n times. Every element enters the window once and leaves at most once, which caps the total pointer movement at 2n. The code reads quadratic and runs linear, and that amortized argument is what keeps the variable-size window an O(n) technique despite the loop nesting.

What to say in the interview: 'I'll use a sliding window because we need the longest/shortest subarray satisfying a condition. I'll expand the right side to include more elements, and shrink from the left when the condition breaks. Let me walk through one iteration.' Then trace through a small example before coding.

Forgetting to shrink the window. Candidates expand correctly but never move the left pointer, turning the "window" into "scan everything from start."

Off-by-one on window size. For fixed-size windows, the window has k elements when right - left + 1 == k. Use right - left == k and you get wrong answers on every test case.

Updating the answer at the wrong time. Update once the window is valid. If you update before shrinking, you're recording invalid states.

What This Section Covers

We open with fixed-size windows, then move to variable-size ones that carry heavier state. By the end, substring problems backed by a hash map should feel routine.

Maximum Sum Subarray of Size KFixed Size

The purest fixed-size window problem

A [[prem:/guides/foundations/sliding-window/find-all-anagrams|question]]Fixed Size

Fixed-size with character frequency matching

A [[prem:/guides/foundations/sliding-window/longest-substring-without-repeating|question]]Variable Size

Variable window with a hash set

A [[prem:/guides/foundations/sliding-window/minimum-window-substring|question]]Variable Size

The "boss level", a variable window with frequency tracking

Sliding Window vs Two Pointers

Both techniques run a left and a right pointer, so they blur together. The mindset is different:

Two Pointers

Usually converging from opposite ends
Or one pointer chasing the other
Focus is on pointer positions
Deciding which pointer to move

Sliding Window

Both pointers move in same direction
Focus is on window contents
Maintaining aggregate state (sum, count, frequencies)
Tracking "what's inside the window"

A sorted-array problem points to two pointers. A substring or subarray problem with a condition to maintain points to sliding window. What separates them: do you care about the endpoints (two pointers) or the contents between them (sliding window)?

The Moving Frame

Sliding window turns O(n×k) into O(n) off one observation: neighboring windows share nearly all their elements, so recomputing each from scratch throws away work you already did.

We start with fixed-size windows, then build up to variable-size ones with hash map state. Every problem drills the same skill: keeping the window state correct and cheap as the frame moves.

Key Takeaways

Sliding window maintains state incrementally as a frame moves across the data
Fixed-size windows: size is given, slide and track (sums, max, anagrams)
Variable-size windows: expand until invalid, shrink until valid, track longest/shortest
The pattern is always: expand → shrink (if needed) → update result
Look for "contiguous subarray/substring" as your signal

Next: Maximum Sum Subarray of Size K