Sliding Window — Fixed Size

Before we start

The first three chapters used two or three pointers to scan individual elements. This chapter introduces a new idea: treating a contiguous block of K elements as a single moving object — a window — that slides across the array. By the end you will be able to:

• See the sliding window as a train compartment gliding along a track.
• Explain why reusing the previous window's result makes this O(n) instead of O(n·K).
• Recognise the fixed-window skeleton in problems about sums, averages, and maximums over K-length subarrays.

Stop at every Pause & Think box before reading on.

Picture this first (no code yet)

The train is the array. The window is a block of K elements. Every shift costs O(1), not O(K).

The actual problem

Given an array of integers and a window size K, find the maximum sum of any K consecutive elements.

Example:

array = [2, 1, 5, 1, 3, 2]
K     = 3

windows: [2,1,5]=8   [1,5,1]=7   [5,1,3]=9   [1,3,2]=6
answer  = 9

First, the slow way (so you feel the pain)

The obvious approach: for every starting position, add up K elements.

def max_sum_slow(arr, k):
    n = len(arr)
    best = float('-inf')
    for i in range(n - k + 1):           # every starting position
        total = 0
        for j in range(i, i + k):        # add K elements
            total += arr[j]
        best = max(best, total)
    return best

For each of the n - k + 1 windows you do k additions. Total work:

n = 10,  k = 3   →  about 24 operations
n = 10,000,  k = 1,000   →  about 9,000,000 operations
n = 100,000, k = 50,000  →  about 2,500,000,000 operations

The second approach is the train trick: reuse what you computed last time.

The turning point

Look at two adjacent windows:

Window 1: arr[0] + arr[1] + arr[2]  =  2 + 1 + 5  =  8
Window 2: arr[1] + arr[2] + arr[3]  =  1 + 5 + 1  =  7

Notice how much they share: arr[1] and arr[2] appear in both. We computed them twice.

The answer: new_sum = old_sum - arr[0] + arr[3].

Subtract the element that left the window on the left. Add the element that entered the window on the right. One subtraction, one addition — the window "slides" forward in O(1) regardless of K.

The one idea to remember

Watch it happen, frame by frame

Array: [2, 1, 5, 1, 3, 2], K = 3.

Step 1 — Build the first window (positions 0, 1, 2):
  window_sum = 2 + 1 + 5 = 8
  best = 8

Step 2 — Slide: remove arr[0]=2, add arr[3]=1
  window_sum = 8 - 2 + 1 = 7
  best = max(8, 7) = 8

Step 3 — Slide: remove arr[1]=1, add arr[4]=3
  window_sum = 7 - 1 + 3 = 9
  best = max(8, 9) = 9

Step 4 — Slide: remove arr[2]=5, add arr[5]=2
  window_sum = 9 - 5 + 2 = 6
  best = max(9, 6) = 9

No more positions. Answer = 9.  ✅

The outgoing element is always at index i - 1 when the new window ends at index i + k - 1. Let's see this with concrete indices:

i=0: window covers [0..2], sum = build from scratch
i=1: remove arr[i-1]=arr[0], add arr[i+k-1]=arr[3]
i=2: remove arr[i-1]=arr[1], add arr[i+k-1]=arr[4]
i=3: remove arr[i-1]=arr[2], add arr[i+k-1]=arr[5]

First window [4,2,1] = 7.   best=7
Slide: -4+7 → [2,1,7]=10.  best=10
Slide: -2+8 → [1,7,8]=16.  best=16
Slide: -1+1 → [7,8,1]=16.  best=16
Slide: -7+2 → [8,1,2]=11.  best=16
Slide: -8+8 → [1,2,8]=11.  best=16
Slide: -1+1 → [2,8,1]=11.  best=16
Slide: -2+0 → [8,1,0]=9.   best=16
Answer = 16 (the window [1,7,8] starting at index 2)

Now, the code — line by line

def max_sum_fixed(arr, k):
    n = len(arr)
    if n < k:
        return None                        # not enough elements for even one window

    # Step 1: Build the first window from scratch
    window_sum = sum(arr[:k])              # add the first k elements
    best = window_sum

    # Step 2: Slide the window across the rest of the array
    for i in range(k, n):                 # i is the index of the incoming element
        window_sum += arr[i]              # add the new element entering on the right
        window_sum -= arr[i - k]          # remove the old element leaving on the left
        best = max(best, window_sum)

    return best

Mapping each line to the train story:

• window_sum = sum(arr[:k]) — tally the first K cars in the window before the train starts moving.
• for i in range(k, n): — for each forward shift of the train (each new car entering the window on the right).
• window_sum += arr[i] — the new car on the right enters the window; add its weight.
• window_sum -= arr[i - k] — the old car on the left exits the window; subtract its weight.
• best = max(best, window_sum) — record the best total seen so far.

The key index relationship: when the incoming element is at index i, the outgoing element is at index i - k (exactly K positions behind).

Why is it correct?

At every step, window_sum equals exactly arr[i-k+1] + arr[i-k+2] + ... + arr[i] — the sum of the K elements ending at position i. We can verify this with the invariant:

• After the first window: window_sum = arr[0] + arr[1] + ... + arr[k-1]. ✓
• After each slide: we add arr[i] and remove arr[i-k], so the sum shifts from covering [i-k..i-1] to covering [i-k+1..i]. The window always covers exactly K consecutive elements. ✓

Since we track the maximum over all valid windows, and we correctly compute every window's sum, the answer is guaranteed correct.

Why is it so fast?

The first window costs O(k) to build. After that, each of the n - k slides costs exactly 2 operations (one add, one subtract). Total: k + 2(n - k) = 2n - k ≈ O(n).

Compare to the brute force:

n = 100,000,  k = 50,000
Slow:  ~2,500,000,000 operations
Fast:  ~150,000 operations   (≈16,000× faster)

When should I reach for this? (the trigger list)

Reach for the fixed-size sliding window when you see:

• The problem asks about every subarray (or substring) of length exactly K.
• Words like "maximum," "minimum," "average," or "count" over a fixed-length window.
• A brute-force solution clearly has a nested loop where the inner loop always runs K times.
• The question involves a contiguous segment — order matters, elements must be adjacent.
• You need O(n) and the window size doesn't change as you slide.

The moment K is fixed and you're computing the same aggregate (sum, max, etc.) repeatedly over overlapping windows — slide, don't recompute.

The same trick in four disguises

Disguise 1 — Average of Subarrays of Size K

Instead of tracking the max sum, track the running average. Same slide formula:

def avg_subarrays(arr, k):
    n = len(arr)
    result = []
    window_sum = sum(arr[:k])
    result.append(window_sum / k)
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        result.append(window_sum / k)
    return result

Identical skeleton. Different output (list of averages instead of one maximum).

Disguise 2 — Maximum of All Subarrays of Size K (LC #239)

Now you want the maximum element (not sum) in each window. Summing doesn't work here — you can't "remove" a maximum arithmetically.

The trick: use a monotonic deque (a double-ended queue that stays sorted). But here's the key insight — the sliding window skeleton is the same. A window of size K still slides one step at a time. Only the data structure inside the window changes.

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()        # stores indices; front is always the max of current window
    result = []

    for i in range(len(nums)):
        # Remove elements outside the window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # Maintain decreasing order (remove smaller elements from back)
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        dq.append(i)
        # Window is complete after first k elements
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

The outer loop slides the window. The deque is just the smarter "aggregate" inside. Same bones.

Disguise 3 — First Negative Number in Each Window of Size K

Find the first negative number in each K-length window:

from collections import deque

def first_negative(arr, k):
    dq = deque()        # stores indices of negative elements
    result = []
    for i in range(len(arr)):
        if arr[i] < 0:
            dq.append(i)
        if dq and dq[0] < i - k + 1:   # front left the window
            dq.popleft()
        if i >= k - 1:
            result.append(arr[dq[0]] if dq else 0)
    return result

Disguise 4 — Count Anagrams (LC #438 — Fixed Char Window)

Find all starting indices in string s where a window of length len(p) is an anagram of p. The window slides across s one character at a time; entering character increments its count, exiting character decrements it.

from collections import Counter

def find_anagrams(s, p):
    k = len(p)
    need = Counter(p)
    have = Counter(s[:k])
    result = [0] if have == need else []

    for i in range(k, len(s)):
        # Add incoming character
        have[s[i]] += 1
        # Remove outgoing character
        outgoing = s[i - k]
        have[outgoing] -= 1
        if have[outgoing] == 0:
            del have[outgoing]
        if have == need:
            result.append(i - k + 1)

    return result

Same slide formula (add incoming, remove outgoing). The "aggregate" is now a frequency counter, not a sum.

Traps that catch beginners

Say it like a pro (interview one-liner)

"Since the window size is fixed at K, I'll compute the first window's sum directly and then slide one position at a time — adding the incoming element on the right and subtracting the outgoing element on the left. This avoids recomputing the K-element sum from scratch each time, reducing the complexity from O(n·K) to O(n)."

Check yourself

Practice problems

When you can code the max-sum solution without notes, explain the outgoing-element index, and state why reuse beats recompute — you have learned this pattern.

Next up: Sliding Window — Variable Size, where the window expands and contracts based on a condition, and the trick is knowing when to shrink.