Identifying the Fixed Sliding Window Pattern

The Diagnostic Questions

If yes to both, you have a fixed sliding window problem.

The Example: Maximum Average Subarray

Problem: Given an array arr and an integer k, find the maximum average of any contiguous subarray of size exactly k.

arr = [1, 12, -5, -6, 50, 3],  k = 4

Subarrays of size 4:
  [1,  12, -5, -6]  →  sum =  2,  avg = 0.50
  [12, -5, -6, 50]  →  sum = 51,  avg = 12.75  ← maximum
  [-5, -6, 50,  3]  →  sum = 42,  avg = 10.50

Answer: 12.75

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  subgraph W1["Window 1: [1, 12, -5, -6]  avg = 0.50"]
    direction LR
    A0["1"] --- A1["12"] --- A2["-5"] --- A3["-6"] --- A4["50"] --- A5["3"]
    PS1(["start=0"]) --> A0
    PE1(["end=3"]) --> A3
  end
  subgraph W2["Window 2: [12, -5, -6, 50]  avg = 12.75 ★"]
    direction LR
    B0["1✗"] --- B1["12"] --- B2["-5"] --- B3["-6"] --- B4["50"] --- B5["3"]
    PS2(["start=1"]) --> B1
    PE2(["end=4"]) --> B4
  end
  subgraph W3["Window 3: [-5, -6, 50, 3]  avg = 10.50"]
    direction LR
    C0["1✗"] --- C1["12✗"] --- C2["-5"] --- C3["-6"] --- C4["50"] --- C5["3"]
    PS3(["start=2"]) --> C2
    PE3(["end=5"]) --> C5
  end
  W1 -->|"remove 1, add 50"| W2
  W2 -->|"remove 12, add 3"| W3

Three windows of size k=4 slide through the array. Each slide removes one element from the left and adds one from the right — the sum updates in O(1) each time.

Applying the Diagnostic Questions

Q1 — Why “fixed size” matters here?

WHAT: The problem asks for the maximum average over subarrays of size exactly k. The window size is a fixed constraint, not a goal to satisfy. Every valid subarray has the same size.

WHY “fixed” is the key qualifier: A fixed window never needs logic to decide whether to grow or shrink based on a condition. You just slide it. This is what separates fixed sliding window from variable sliding window — in the variable version, the window size changes dynamically to satisfy a condition (e.g., “smallest subarray with sum ≥ target”). Here, the size is always k. No condition checking needed to adjust the window.

Concrete check: With k=4 and n=6, there are exactly n − k + 1 = 3 valid windows. Each has exactly 4 elements. The brute force computes the sum of 4 elements, 3 times — that’s 12 additions. The sliding window computes the initial window once (4 additions) and then 2 slides (2 additions + 2 subtractions = 4 more operations) — 8 total. As k grows, this advantage compounds dramatically.

What breaks if you use variable sliding window logic here: A variable window expands and contracts based on whether a condition is satisfied. With a fixed target size, there’s no condition to check — every window of size k is valid. Using variable logic would add unnecessary complexity without any benefit.

Q2 — Why “O(1) add and remove” is required?

WHAT: When the window slides right by 1:

• arr[end] enters the window → sum += arr[end]
• arr[start] leaves the window → sum -= arr[start]

Both operations are O(1) arithmetic on a single variable.

WHY this is the condition that makes sliding window faster than brute force: Brute force recomputes the sum of k elements from scratch for every window — O(k) per window, O(N × k) total. Sliding window reuses the previous sum and updates it in O(1) — O(N) total. The update must be O(1), or the sliding window gains nothing over brute force.

What doesn’t have O(1) remove: “Maximum element in window” — when the maximum element leaves the window, you need to find the new maximum from the remaining k−1 elements. That’s O(k), not O(1). Fixed sliding window doesn’t apply; you’d need a monotonic deque instead. “Sum of squares” could be O(1) (+= end², -= start²), so it does apply. Always verify both add AND remove are O(1) before using this pattern.

Brute Force: Nested Loops, O(N × k)

Fix a starting index i, compute the sum of k elements starting there, check if it beats the current max:

from typing import List

def k_subarray_max_average_brute(arr: List[int], k: int) -> float:
    n = len(arr)
    max_average = float('-inf')  # Start below any possible average

    # Outer loop: try every valid starting position (last valid start is n-k)
    for i in range(n - k + 1):
        current_sum = 0

        # Inner loop: sum the k elements starting at index i
        # This recomputes elements arr[i+1..i+k-1] that were already summed in the previous window
        for j in range(k):
            current_sum += arr[i + j]

        max_average = max(max_average, current_sum / k)

    return max_average

print(k_subarray_max_average_brute([1, 12, -5, -6, 50, 3], 4))  # 12.75

n=6,  valid starting positions: i = 0, 1, 2  (n - k + 1 = 3)

i=0: j=0..3 → 1 + 12 + (-5) + (-6) = 2    → avg = 0.50   max_avg = 0.50
i=1: j=0..3 → 12 + (-5) + (-6) + 50 = 51  → avg = 12.75  max_avg = 12.75
              Note: 12, -5, -6 were already summed in i=0 — recomputed here
i=2: j=0..3 → (-5) + (-6) + 50 + 3 = 42   → avg = 10.50  max_avg = 12.75
              Note: -5, -6, 50 were already summed in i=1 — recomputed again

Return: 12.75 ✓

Total additions: 3 windows × 4 elements = 12 additions
Sliding window would do: 4 (initial) + 2×2 (slides) = 8 operations

Fixed Sliding Window Solution: One Pass, O(N)

Keep a running window_sum. As end advances, add arr[end]. Once the window exceeds size k, remove arr[start] and advance start. When the window is exactly k, check against max_average:

from typing import List

class Solution:
    def k_subarray_max_average(self, arr: List[int], k: int) -> float:
        n           = len(arr)
        start       = 0             # Left boundary of the current window
        end         = 0             # Right boundary of the current window
        window_sum  = 0             # Running sum of elements in the current window
        max_average = float('-inf') # Best average seen so far across all windows

        while end < n:
            # ① Expand: bring arr[end] into the window
            window_sum += arr[end]

            # ② Contract: if window grew past k, evict the leftmost element
            if end - start + 1 > k:
                window_sum -= arr[start]  # Remove arr[start]'s contribution
                start += 1               # Shrink from the left

            # ③ Process: when window is exactly k elements, check the average
            if end - start + 1 == k:
                # Divide sum by k to get average — we store sum to avoid repeated division
                max_average = max(max_average, window_sum / k)

            end += 1  # Expand the window rightward for the next iteration

        return max_average

print(Solution().k_subarray_max_average([1, 12, -5, -6, 50, 3], 4))  # 12.75

start=0, end=0, window_sum=0, max_average=-inf

end=0: window_sum += arr[0]=1  → sum=1.  size=1, not k=4.
end=1: window_sum += arr[1]=12 → sum=13. size=2.
end=2: window_sum += arr[2]=-5 → sum=8.  size=3.
end=3: window_sum += arr[3]=-6 → sum=2.  size=4 == k → avg=2/4=0.50.   max_avg=0.50.
end=4: window_sum += arr[4]=50 → sum=52. size=5 > k → remove arr[0]=1: sum=51, start=1.
       size=4 == k → avg=51/4=12.75. max_avg=12.75.
end=5: window_sum += arr[5]=3  → sum=54. size=5 > k → remove arr[1]=12: sum=42, start=2.
       size=4 == k → avg=42/4=10.50. max_avg=12.75.
end=6: end >= n=6 → loop exits.

Return: 12.75 ✓

Total operations: 6 adds + 2 removes = 8 (vs 12 for brute force on this input)
Every element added exactly once, removed at most once.

Problems in This Category

All follow the same template — the only thing that changes is the add and remove logic in steps ① and ②.