Fixed-Size Sliding Window

Given an array of integers and a number k, find the maximum sum of any k consecutive elements. For example, in the array [2, 1, 5, 1, 3, 2] with k = 3, the answer is 9, from the subarray [5, 1, 3].

The naive approach computes the sum of each window from scratch: for every starting index i, sum up the elements from i to i + k - 1. That is $O(n \cdot k)$ work, which is slow when k is large. But notice that consecutive windows overlap almost entirely. When the window slides one position to the right, you lose one element on the left and gain one element on the right. Everything in between stays the same. So instead of recomputing the sum, you subtract the element leaving the window and add the element entering it. Each slide costs $O(1)$ instead of $O(k)$.

Walking through [2, 1, 5, 1, 3, 2] with k = 3

Start by computing the sum of the first window: 2 + 1 + 5 = 8. This is our initial best.

Slide to the next window. Subtract the element leaving (2) and add the element entering (1). Sum: 8 - 2 + 1 = 7. Window is [1, 5, 1]. Best is still 8.

Slide again. Subtract 1, add 3. Sum: 7 - 1 + 3 = 9. Window is [5, 1, 3]. Best is now 9.

Slide once more. Subtract 5, add 2. Sum: 9 - 5 + 2 = 6. Window is [1, 3, 2]. Best is still 9.

We have exhausted all windows. The answer is 9. We computed the initial sum in $O(k)$ and then did $n - k$ slides at $O(1)$ each, for a total of $O(n)$.

Code for maximum sum of size k

def maxSumWindow(nums, k):
    window_sum = sum(nums[:k])
    best = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        best = max(best, window_sum)
    return best

The expression nums[i] - nums[i - k] is the heart of the technique: nums[i] is the new element entering the window on the right, and nums[i - k] is the old element leaving on the left. This one-line update replaces an entire inner loop.

How fixed-size differs from variable-size sliding windows

In variable-size sliding window problems, the window grows and shrinks dynamically: you expand the right edge, then use a while loop to shrink the left edge when a constraint is violated. The window size changes throughout the algorithm.

In fixed-size problems, the window is always exactly k elements wide. There is no shrinking decision to make. You compute the first window, then slide one step at a time, and that is the entire algorithm. The code is simpler and the logic is more mechanical, but the insight, avoid redundant computation by reusing the previous window's result, is the same.

Maximum average subarray

LeetCode 643 asks you to find the contiguous subarray of length k with the highest average, given an array and integer k. The code is identical to maximum sum: just divide the best sum by k at the end.

def findMaxAverage(nums, k):
    window_sum = sum(nums[:k])
    best = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        best = max(best, window_sum)
    return best / k

This works because the window size is constant, so maximizing the sum is equivalent to maximizing the average. You do not need to track the average at each step.

Sliding window maximum: when a simple variable is not enough

Take LeetCode 239: you are given an array and integer k, and must return the maximum element in each window of size k. For the array [1, 3, -1, -3, 5, 3, 6, 7] with k = 3, the output is [3, 3, 5, 5, 6, 7].

You might think you can track the maximum with a single variable, updating it as elements enter and leave. But here is the problem: when the current maximum leaves the window, you have no way to know what the new maximum is without scanning the entire window. That scan costs $O(k)$ per slide, giving $O(n \cdot k)$ overall, no better than brute force.

The solution is a monotonic deque (double-ended queue). The deque stores indices of elements in decreasing order of their values. When a new element enters the window, you remove all elements from the back of the deque that are smaller than it (they can never be the maximum while the new element is in the window). When the element at the front of the deque falls outside the window, you remove it from the front. The maximum for the current window is always the element at the front of the deque.

This is a rich enough topic that it deserves its own dedicated treatment. See the monotonic deque article for a full walkthrough with code. The key point for now is that when the window property you are tracking cannot be maintained with a simple running value (like a sum), you need a more sophisticated data structure inside the window.

Finding all anagrams: character frequency maps in the window

For LeetCode 438, you are given a string s and a pattern p, and must find all starting indices in s where an anagram of p begins. For s = "cbaebabacd" and p = "abc", the output is [0, 6] because "cba" starts at index 0 and "bac" starts at index 6.

An anagram of p is any substring that has exactly the same character frequencies as p. Since all anagrams of p have the same length as p, this is a fixed-size window problem with k = len(p). You slide a window of size k across s and check whether the character frequencies in the window match those in p.

Walking through "cbaebabacd" with pattern "abc"

The pattern "abc" has frequency: a=1, b=1, c=1. We use a window of size 3.

Window at index 0: "cba". Frequencies: a=1, b=1, c=1. This matches the pattern. Record index 0.

Slide to index 1: remove 'c', add 'e'. Window "bae". Frequencies: a=1, b=1, e=1. Does not match.

Slide to index 2: remove 'b', add 'b'. Window "aeb". Frequencies: a=1, b=1, e=1. Does not match.

Slide to index 3: remove 'a', add 'a'. Window "eba". Frequencies: a=1, b=1, e=1. Does not match.

Slide to index 4: remove 'e', add 'b'. Window "bab". Frequencies: a=1, b=2. Does not match.

Slide to index 5: remove 'b', add 'a'. Window "aba". Frequencies: a=2, b=1. Does not match.

Slide to index 6: remove 'a', add 'c'. Window "bac". Frequencies: a=1, b=1, c=1. This matches. Record index 6.

Slide to index 7: remove 'b', add 'd'. Window "acd". Frequencies: a=1, c=1, d=1. Does not match.

The result is [0, 6].

Code for finding all anagrams

The trick for efficiency is to avoid comparing entire frequency maps at each step. Instead, track how many characters still need to be matched. When a character enters the window and its count goes from "needed" to "satisfied," decrement a matches_needed counter. When a character leaves and its count goes from "satisfied" to "needed," increment the counter. The window is a valid anagram when matches_needed reaches zero.

from collections import Counter

def findAnagrams(s, p):
    if len(p) > len(s):
        return []

    p_count = Counter(p)
    s_count = Counter()
    result = []
    k = len(p)
    matches_needed = len(p_count)
    matches = 0

    for i in range(len(s)):
        # Add character entering the window
        char_in = s[i]
        s_count[char_in] += 1
        if char_in in p_count and s_count[char_in] == p_count[char_in]:
            matches += 1

        # Remove character leaving the window
        if i >= k:
            char_out = s[i - k]
            if char_out in p_count and s_count[char_out] == p_count[char_out]:
                matches -= 1
            s_count[char_out] -= 1

        # Check if current window is an anagram
        if matches == matches_needed:
            result.append(i - k + 1)

    return result

The matches variable counts how many distinct characters have exactly the right frequency. When it equals matches_needed (the number of distinct characters in p), every character frequency matches and the window is an anagram. Each slide updates at most two characters, so the comparison is $O(1)$ per step.

Complexity analysis

For all standard fixed-size sliding window problems, the time complexity is $O(n)$. You spend $O(k)$ building the initial window and $O(n-k)$ sliding it, with $O(1)$ work per slide. Since k <= n, the total is $O(n)$.

Space complexity depends on what you store in the window. For sum-based problems, it is $O(1)$: you just track a running total. For frequency-map problems like the anagram finder, it is $O(alphabet)$, where the alphabet is typically 26 lowercase letters or 128 ASCII characters. For the sliding window maximum with a monotonic deque, the space is $O(k)$ since the deque holds at most $k$ elements.

The fixed-size sliding window is one of the simplest and most widely applicable algorithmic patterns. Any time a problem asks you about "all contiguous subarrays of size k," your first instinct should be to reach for this technique. The only question is what data structure you need inside the window to track the property you care about: a running sum, a frequency map, or something like a monotonic deque.

Recognizing this pattern

You're probably looking at a fixed-size sliding window when:

• The problem says "subarray / substring of size exactly k," "window of length k," "every k consecutive elements," or "all subarrays of length k."
• k is an explicit input. You are not deciding the window size, the problem dictates it.
• You need to compute the same aggregate (sum, max, frequency match, average) for every window of size k.
• Recomputing each window from scratch is the obvious $O(n \cdot k)$ baseline.
• The aggregate has a cheap "add the new right element, remove the old left element" update: running sum, character counter, monotonic deque, etc.

Common templates:

• Running sum / average: window_sum += nums[i] - nums[i - k]. Example: Maximum Average Subarray I.
• Frequency-map match against a pattern: fixed window of len(p), track matches counter. Example: Find All Anagrams in a String.
• Monotonic deque for window max/min: push indices in decreasing/increasing order, pop stale front. Example: Sliding Window Maximum.
• Boolean check across all length-k windows: slide, test predicate at each step, return on first success. Example: Contains Duplicate II.
• Running aggregate with threshold: count windows whose sum/average crosses a bound. Example: K Radius Subarray Averages.