Understanding the Fixed Sliding Window Pattern

The Problem: Recomputing Overlapping Work

Some problems ask you to compute something (a sum, an average, a count) over every contiguous subarray of size k. The naive approach uses nested loops: for each starting position i, loop through k elements and compute the result. That’s O(N × k).

But here’s the waste: when the window shifts one step to the right, k − 1 elements are shared between the old window and the new one. You’re recomputing the contribution of those shared elements from scratch every time.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart LR
  subgraph W1["Window 1: [1, 2, 3, 4]  sum=10"]
    direction LR
    A["1"] --- B["2"] --- C["3"] --- D["4"]
  end
  subgraph W2["Window 2: [2, 3, 4, 5]  sum=14"]
    direction LR
    E["2"] --- F["3"] --- G["4"] --- H["5"]
  end
  W1 -->|"slide right by 1"| W2
  NOTE["sum = 10 − 1 + 5 = 14<br/>Remove arr[0], add arr[4]<br/>No need to recompute 2+3+4"]
  W2 --- NOTE

When the window slides right by 1, only one element leaves and one enters. The sum updates in O(1) by subtracting the outgoing element and adding the incoming one.

The fixed sliding window technique avoids the recomputation by maintaining a running aggregate and updating it with a single add (for the new element entering the window) and a single remove (for the element leaving the window). One pass, O(N) total.

What “Fixed Size” Means

A fixed-size window is a contiguous subarray of exactly k elements, defined by two boundaries: start and end. As the window slides, end moves right to bring a new element in, and start moves right to push the old element out.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
block-beta
  columns 8
  A["1"] B["2"] C["3"] D["4"] E["5"] F["6"] G["7"] H["8"]
  START["↑ start"]:1 SPAN["← window (k=4) →"]:3 ENDD["↑ end"]:1 EMPTY[" "]:3

A fixed window of size k=4 in an array of 8 elements — start points at the leftmost element of the window, end at the rightmost.

Window size invariant: end − start + 1 == k when a full window is formed. The window slides by incrementing both start and end by 1 each step, keeping the size locked at k.

The Three Events Per Step

Each iteration of the main loop has three events in sequence:

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart LR
  E1["① Add arr[end]<br/>to aggregate"]
  E2{"② Window size<br/>> k ?"}
  E3["Remove arr[start]<br/>from aggregate<br/>start += 1"]
  E4{"③ Window size<br/>== k ?"}
  E5["Process aggregate<br/>(record result)"]
  E6["end += 1"]

  E1 --> E2
  E2 -->|"yes"| E3 --> E4
  E2 -->|"no"| E4
  E4 -->|"yes"| E5 --> E6
  E4 -->|"no"| E6

Three events per iteration — expand right (add), contract left if oversized (remove), record if full-sized window.

Why expand first, then contract? Because we want to check every possible window, including the one that just formed. If we contracted before expanding, we’d skip the step where end first reaches a valid position. Expand → check size → process is the correct order.

Watching the Window Slide

Let’s trace through arr = [1, 2, 3, 4, 5] with k = 3 to see every window:

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  subgraph S0["end=2: window=[1,2,3] size=3==k → sum=6"]
    direction LR
    A0["1"] --- A1["2"] --- A2["3"] --- A3["4"] --- A4["5"]
    P0S(["start=0"]) --> A0
    P0E(["end=2"]) --> A2
  end
  subgraph S1["end=3: add 4, remove 1 → window=[2,3,4] sum=9"]
    direction LR
    B0["1✗"] --- B1["2"] --- B2["3"] --- B3["4"] --- B4["5"]
    P1S(["start=1"]) --> B1
    P1E(["end=3"]) --> B3
  end
  subgraph S2["end=4: add 5, remove 2 → window=[3,4,5] sum=12"]
    direction LR
    C0["1✗"] --- C1["2✗"] --- C2["3"] --- C3["4"] --- C4["5"]
    P2S(["start=2"]) --> C2
    P2E(["end=4"]) --> C4
  end
  S0 -->|"end++ → 3"| S1
  S1 -->|"end++ → 4"| S2

The window slides right one step at a time — each slide removes the leftmost element and adds the next rightmost. Sum updates in O(1) per slide.

The Template

from typing import List

def fixed_size_sliding_window(arr: List[int], k: int) -> None:
    start     = 0  # Left boundary of the window
    end       = 0  # Right boundary of the window (expands every iteration)
    aggregate = 0  # Running value of the aggregate function over the current window

    while end < len(arr):
        # ① Expand: add the contribution of the new element entering from the right
        aggregate += arr[end]   # Replace with f_add(aggregate, arr[end]) for other functions

        # ② Contract: if the window grew past size k, remove the leftmost element
        if end - start + 1 > k:
            aggregate -= arr[start]   # Replace with f_remove(aggregate, arr[start])
            start += 1                # Shrink the window from the left

        # ③ Process: when window is exactly size k, record or compare the aggregate
        if end - start + 1 == k:
            pass  # Record aggregate, update max/min, etc.

        # Advance the right boundary to bring in the next element next iteration
        end += 1

When Can This Technique Be Applied?

The fixed sliding window requires the aggregate function to support both an add operation and a remove operation, both in O(1).

Why max/min don’t work: When the maximum element leaves the window, you need to find the new maximum of the remaining k−1 elements. That’s an O(k) scan — removing in O(1) isn’t possible with just a single variable. These problems need a deque or heap instead.

Complexity

end moves from 0 to N−1 exactly once. start moves from 0 to at most N−k exactly once. Every element is added to aggregate once and removed from aggregate at most once:

Compared to the nested-loop brute force which is O(N × k), the sliding window reduces the inner loop from k iterations to O(1) by reusing the aggregate from the previous window.