Fixed-Size Sliding Window: Maximum Sum of a Size-k Window

A fixed-size sliding window keeps a window of a constant width k and slides it across the array one step at a time, updating a running summary instead of recomputing it. The headline use case: find the maximum sum of any contiguous subarray of length k in a single O(n) pass.

The naive way (and why it’s slow)

For each of the n - k + 1 starting positions you could add up k elements: that’s O(n·k). When k is large this approaches O(n²). The waste is obvious — neighboring windows overlap in k - 1 elements, so we keep re-adding the same numbers.

The sliding trick

Compute the sum of the first window once. Then, to move one step right, add the new element and subtract the one that fell off the left. Each step is O(1), so the whole sweep is O(n).

// Maximum sum of any contiguous subarray of length k.
#include <vector>
#include <algorithm>
int maxSumWindow(const std::vector<int>& a, int k) {
    int n = a.size();
    if (n < k) return 0; // or signal invalid input
    int sum = 0;
    for (int i = 0; i < k; i++) sum += a[i]; // first window
    int best = sum;
    for (int r = k; r < n; r++) {
        sum += a[r] - a[r - k];              // slide by one
        best = std::max(best, sum);
    }
    return best;
}

// Maximum sum of any contiguous subarray of length k.
int maxSumWindow(int[] a, int k) {
    int n = a.length;
    if (n < k) return 0; // or signal invalid input
    int sum = 0;
    for (int i = 0; i < k; i++) sum += a[i]; // first window
    int best = sum;
    for (int r = k; r < n; r++) {
        sum += a[r] - a[r - k];              // slide by one
        best = Math.max(best, sum);
    }
    return best;
}

// Maximum sum of any contiguous subarray of length k.
function maxSumWindow(a, k) {
  const n = a.length;
  if (n < k) return 0; // or signal invalid input
  let sum = 0;
  for (let i = 0; i < k; i++) sum += a[i]; // first window
  let best = sum;
  for (let r = k; r < n; r++) {
    sum += a[r] - a[r - k];                 // slide by one
    best = Math.max(best, sum);
  }
  return best;
}

# Maximum sum of any contiguous subarray of length k.
def max_sum_window(a, k):
    n = len(a)
    if n < k:
        return 0  # or signal invalid input
    s = sum(a[:k])      # first window
    best = s
    for r in range(k, n):
        s += a[r] - a[r - k]  # slide by one
        best = max(best, s)
    return best

Tracing it

For a = [2, 1, 5, 1, 3, 2], k = 3:

[2 1 5] 1 3 2   -> 8     (first window)
2 [1 5 1] 3 2   -> 7     (+1, -2)
2 1 [5 1 3] 2   -> 9     (+3, -1)  <- best
2 1 5 [1 3 2]   -> 6     (+2, -5)
answer = 9

Complexity

• Time: O(n) — one pass; each slide is O(1).
• Space: O(1) — just the running sum and the best value.

The same skeleton solves any fixed-window aggregate: maximum average (divide the best sum by k), counting windows whose sum meets a threshold, or the maximum of each window (that variant uses a monotonic deque to stay O(n)).

For beginners: The window width never changes here — that’s what makes it fixed. If the problem instead asks for the longest or shortest window meeting a rule, the width must flex; use the variable-size window.

Common pitfalls

• Recomputing the whole window. If you re-sum k elements every step you’re back to O(n·k). Add-one, subtract-one is the whole point.
• Off-by-one on the boundary. The element leaving is a[r - k], not a[r - k + 1]. Trace a tiny example to confirm.
• Window larger than the array. Guard n < k before building the first window, or you’ll read out of bounds.
• Integer overflow. For large values or large k, use a 64-bit accumulator (long long / long).

Going deeper: When elements can be negative and you want the best sum over any length (not a fixed k), this pattern no longer applies — that’s Kadane’s algorithm. Fixed-window is for a fixed width only.

Next: handle windows that resize with the variable-size window, or test yourself on the exercises.