L09 · Sliding Window I — Fixed Size

Series: LeetCode — From Basics to Interview-Ready · Session 9 / 65 · Phase 1 · Core patterns

Watch first

What this pattern IS

Many problems ask about every contiguous block of exactly k elements: the max sum of any k consecutive numbers, the average of every window of k, whether any window of length k is an anagram of a target.

The obvious approach: for each starting index, sum up the k elements. That's n starting positions times k work each = O(n·k). For a million-element array and k = 1000, that's a billion operations — too slow.

The insight: consecutive windows overlap in all but two elements. Window [i, i+k) and window [i+1, i+k+1) share k−1 elements. So instead of recomputing the whole sum, add the one element that entered on the right and subtract the one that left on the left. That's O(1) per slide, O(n) total.

The naive scan throws away work; the sliding window reuses it.

First principles

The templates

Template A — running numeric aggregate (sum, then derive average)

def fixed_window_best_sum(nums, k):
    """Max sum of any k consecutive elements."""
    window = sum(nums[:k])          # build the first window explicitly, O(k)
    best = window
    for right in range(k, len(nums)):   # right = index of the ENTERING element
        window += nums[right]           # add the entering element
        window -= nums[right - k]       # drop the element that just left
        best = max(best, window)
    return best

Two invariants: after processing index right, window holds the sum of exactly the k elements ending at right; and right - k is always the index that just fell out of the window.

Template B — fixed window over a frequency map

from collections import Counter
 
def fixed_window_counts(s, k):
    """Slide a size-k window and keep a live Counter of its characters."""
    win = Counter(s[:k])            # first window's letter counts
    # ... check win here for the first window ...
    for right in range(k, len(s)):
        win[s[right]] += 1          # entering char
        left = s[right - k]         # leaving char
        win[left] -= 1
        if win[left] == 0:
            del win[left]           # keep the map clean so len(win) means "distinct in window"
        # ... check win here ...
    return None

Deleting zero-count keys is the detail people forget; it keeps len(win) equal to the number of distinct characters actually in the window.

Mental model

Memory / mnemonic

The whole pattern is two arithmetic lines. Peg them with "IN then OUT, then check."

• IN = window += nums[right] — the new element boards.
• OUT = window -= nums[right - k] — the oldest element leaves.
• CHECK = update your answer.

Say the index rhyme: "right enters, right-minus-k exits." If you ever write right - k + 1 or left = 0, you've broken the frame — the leaving index is always exactly k behind the entering one.

For the count variant, add a fourth beat: "IN, OUT, CLEAN, check" — CLEAN = delete the zero-count key.

The trap

What interviewers actually ask

Fixed-window questions are common warm-ups and set up the harder variable-window problems in L10–L11.

• Maximum Average Subarray I (643) · Easy · Amazon — probes: do you slide with add/drop or naively recompute? Follow-up: what if k can change between queries (precompute prefix sums, L12)?
• Best Time to Buy and Sell Stock (121) · Easy · Amazon, Microsoft — probes: a running-min one-pass, the degenerate window. Follow-up: multiple transactions (122), then with cooldown (309).
• Find All Anagrams in a String (438) · Medium · Meta, Amazon — probes: fixed window + count-match in O(1) per slide. Follow-up: return count of matches vs the indices.
• Permutation in String (567) · Medium · Meta, Amazon — probes: fixed window equal to a permutation via a match counter. Follow-up: case-insensitive / unicode.
• Sliding Window Maximum (239) · Hard · Amazon, Google — probes: max is NOT O(1)-updatable — you need a monotonic deque (this is why L18 exists). Follow-up: sliding minimum, or the median (harder).
• Maximum Number of Vowels in a Substring of Given Length (1456) · Medium · Amazon — probes: fixed window over a boolean predicate (is-vowel). Follow-up: generalise to any character class.

Universal probe: "can you avoid recomputing the window each time?" If you say yes and code the add/drop cleanly, you've passed the fixed-window bar.

Worked solutions

1. Maximum Average Subarray I (643)

Plain words: given an array and integer k, find the contiguous subarray of length k with the largest average, and return that average.

Brute force: for each of the n − k + 1 starts, sum k elements and divide. O(n·k). Insight: max average ↔ max sum (k is fixed), and the sum slides in O(1).

def findMaxAverage(nums, k):
    window = sum(nums[:k])           # first window, O(k)
    best = window
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]   # add entering, drop leaving
        best = max(best, window)
    return best / k                  # convert the best sum to an average

Complexity: O(n) time, O(1) memory. Follow-up — "answer many queries with different k": precompute a prefix-sum array once, then each window sum is a subtraction (L12).

def maxAvgStart(nums, k):
    window = sum(nums[:k])
    best, best_start = window, 0
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]
        if window > best:
            best, best_start = window, right - k + 1
    return best_start

2. Find All Anagrams in a String (438)

Plain words: given strings s and p, return the start indices of every substring of s that is an anagram of p (same letters, any order).

Brute force: for each window, sort or count and compare to p's counts — O(n·k) or worse. Insight: keep a live Counter of the current window; compare to p's Counter. Comparing two Counters is O(alphabet) = O(1) for lowercase letters.

from collections import Counter
 
def findAnagrams(s, p):
    if len(p) > len(s):
        return []
    need = Counter(p)
    win = Counter(s[:len(p)])        # first window
    res = []
    if win == need:
        res.append(0)
    for right in range(len(p), len(s)):
        win[s[right]] += 1                 # entering char
        left = s[right - len(p)]           # leaving char
        win[left] -= 1
        if win[left] == 0:
            del win[left]                  # keep counts clean for == to work
        if win == need:
            res.append(right - len(p) + 1) # window start index
    return res

Complexity: O(n) time, O(1) extra (26-letter map). Follow-up — "just count matches": replace the list with an integer counter. A faster variant tracks a single matches integer instead of comparing whole Counters (the L11 technique).

3. Best Time to Buy and Sell Stock (121)

Plain words: one buy then one later sell; maximise profit. This is a degenerate window — a running minimum.

def maxProfit(prices):
    lowest = float('inf')         # cheapest price seen so far (left edge candidate)
    best = 0
    for price in prices:          # right edge sweeps forward
        lowest = min(lowest, price)   # update the best day to have bought
        best = max(best, price - lowest)  # best sale today
    return best

Complexity: O(n) time, O(1) memory. Follow-up — "as many transactions as you like" (122): sum every positive day-to-day gain.

Tradeoff

Where this shows up

Fixed-window sums are the basis of the simple moving average used everywhere in signal processing and finance dashboards: a moving average of period k is exactly this add-one-drop-one sum divided by k. Streaming metrics systems (rate-per-last-k-seconds) use the same incremental update so that each new data point costs O(1) rather than re-summing a buffer.

Checkpoint

Quiz

Practice queue

+7d / +21d mark spaced-repetition anchors.

• Maximum Average Subarray I (643) — Easy · the canonical fixed window · +7d anchor.
• Best Time to Buy and Sell Stock (121) — Easy · degenerate running-min window.
• Maximum Number of Vowels in a Substring of Given Length (1456) — Medium · boolean-predicate window.
• Find All Anagrams in a String (438) — Medium · count-match window · +21d anchor.
• Permutation in String (567) — Medium · fixed window = permutation.
• Sliding Window Maximum (239) — Hard · why max needs a deque (previews L18).
• Substrings of Size Three with Distinct Characters (1876) — Easy · tiny fixed window warm-up.