Sliding Window I — Fixed Size

Review boundary and corrected contracts

A numeric window needs 1 ≤ k ≤ len(nums). Counter equality in Python 3.10+ treats absent entries as zero; deleting zeros is useful for distinct-key counts, not required for equality. Comparing full counters costs the number of distinct keys.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Own the fixed-size sliding window: add the entering element, drop the leaving element, and keep a running aggregate so every slide is O(1).

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

Prerequisites. None beyond basic Python: lists, a for loop with range, and a dictionary/Counter. L07–L08 (two pointers) build the same "two indices" muscle but are not required here.

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.

For n items and 1 <= k <= n, there are n−k+1 complete windows. Recomputing each sum visits k(n−k+1) elements, an O(nk) upper bound. For n=1,000,000 and k=1,000 that is 999,001,000 visits; the count motivates reuse without proving a universal timeout. When k=n, there is only one window, so naive recomputation is linear in that case.

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.

A bus of fixed capacity

Real: A bus holds exactly k passengers. At each stop one new passenger boards at the back and, to stay at capacity, one leaves from the front. You don't recount everyone — you adjust by +1 in and −1 out.

total += nums[right]; total -= nums[right - k] — one element enters, one leaves, count stays k.

First principles

Question: Why can a window aggregate be maintained in O(1) per slide instead of O(k)?

Premise: Adjacent windows of size k differ in exactly two elements.

Because: Sliding right by one drops the leftmost old element and adds one new rightmost element; the middle k−1 are unchanged.

Premise: A sum (or count) is a decomposable aggregate: new = old − leaving + entering.

Because: Integer addition has an inverse, so the outgoing contribution can be removed exactly. Floating-point add/subtract can accumulate rounding error; these numerical examples assume bounded integers before any final division.

Premise: After building the first window, there are n−k slides, yielding n−k+1 window results. Each sum update uses constant work in the bounded-integer model.

Because: The whole array is traversed once with constant work per step.

Premise: Not every aggregate is O(1)-updatable this way (e.g. maximum).

Because: When the maximum leaves, one number does not reveal the next maximum. A monotonic deque gives amortized O(1) updates; heaps or other structures are alternatives with different costs.

Conclusion: Fixed-size window = incremental aggregate. Works cleanly for sum/count; needs extra structure for min/max.

The templates

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

def fixed_window_best_sum(nums, k):
    """Max sum for a bounded-integer sequence; requires 1 <= k <= len(nums)."""
    window = sum(nums[i] for i in range(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[i] for i in range(k))  # no temporary length-k substring
    # ... 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

This is a state-maintenance template, not a finished query: it deliberately returns None where the comments mark caller-specific checks. It requires 1 <= k <= len(s). Deleting zeros keeps len(win) equal to live distinct characters. Python 3.10+ Counter equality treats missing keys as zero, so cleanup is not required for equality correctness. Updating two counts is expected O(1); scanning/copying/comparing the whole map costs its number of stored keys.

Mental model

Name: Add one, drop one

Picture: A rigid frame of width k slides right. Each step: +entering (index right), −leaving (index right − k). The frame never changes size. Check the answer after each adjustment.

• Build the first window in O(k), then slide.

• right is the entering index; right − k is the leaving index.

• Sum and single-count updates are O(1) under the stated model; a monotonic deque supports min/max with amortized O(1) updates.

• Keep count maps clean — delete keys that hit zero.

Trigger: 'every window of size k', 'consecutive k elements', 'subarray of length exactly k', or 'fixed-length anagram/substring'.

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." In this template the leaving index is right-k; right-k+1 instead names the new window start after the slide, as used in maxAvgStart below. Other templates may maintain an explicit left pointer; derive its meaning rather than banning a variable name.

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

The trap

Myth: For a fixed window you should recompute the aggregate over the whole window on each step to be safe.

Truth: That reintroduces the O(n·k) cost you were trying to kill. The entire point is the O(1) incremental update: add entering, subtract leaving.

Why: Adjacent windows share k−1 elements; recomputing rescans those shared elements needlessly. Only two elements ever change per slide.

Test: On small bounded arrays, compare the incremental answers to direct per-window sums, including all-negative values, k=1 and k=n. Count element visits before trying a large benchmark. Neither approach finishes “instantly,” and elapsed-time ratios depend on the machine, runtime and k.

What reviewers 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 · Practice selection. — 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 · Practice selection. — a contrast: a running minimum over an expanding prefix, not a fixed-width window. Follow-up: multiple transactions (122), then with cooldown (309).
• Find All Anagrams in a String (438) · Medium · Practice selection. — fixed window plus count equality; full-map comparison is constant only for a fixed bounded alphabet. Follow-up: return count of matches vs the indices.
• Permutation in String (567) · Medium · Practice selection. — probes: fixed window equal to a permutation via a match counter. Follow-up: case-insensitive / unicode.
• Sliding Window Maximum (239) · Hard · Practice selection. — a single running maximum is insufficient after expiration; a monotonic deque provides amortized O(1) per update (L18). Follow-up: sliding minimum, or the median (harder).
• Maximum Number of Vowels in a Substring of Given Length (1456) · Medium · Practice selection. — probes: fixed window over a boolean predicate (is-vowel). Follow-up: generalise to any character class.

A useful self-check is whether the maintained state suffices after expiration, what each answer check costs, and whether every full window—including the first and last—is evaluated. This is not an interview pass/fail rubric.

Worked solutions

1. Maximum Average Subarray I (643)

Plain words: for bounded integer values and 1 <= k <= len(nums), return the largest average among all contiguous size-k ranges. Empty input or an out-of-range k is outside this function’s contract. The integer running sum is exact; the returned division is a floating-point approximation.

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[i] for i in range(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 and O(1) auxiliary memory over the existing input; the generator initializer avoids the original O(k) temporary slice. For many specified [left,right) range-sum queries, a prefix array gives O(1) per query after O(n) setup and storage. Finding the maximum over all windows of a newly supplied k still examines n−k+1 candidate ranges; prefix sums do not make that maximum query constant-time.

Goal: Return the STARTING INDEX of the max-average window, not the average.

Hint: Track best_start alongside best; update both when window beats best.

def maxAvgStart(nums, k):
    window = sum(nums[i] for i in range(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

The strict window > best update makes maxAvgStart return the earliest start when averages tie. Its initializer has the same numeric and k contract.

2. Find All Anagrams in a String (438)

Plain words: for lowercase ASCII strings s and nonempty p, return every start of a contiguous substring with the same letter multiset as p. If p is longer than s, return an empty list. General Unicode code-point strings can also use these operations, but the fixed-26-alphabet time/space bound would no longer apply; normalization semantics are not defined here.

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[i] for i in range(len(p)))  # first window, no slice allocation
    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]                  # optional cleanup; Counter equality treats missing as zero in Python 3.10+
        if win == need:
            res.append(right - len(p) + 1) # window start index
    return res

Complexity for lowercase ASCII: expected O(n+len(p)) time with at most 26 count entries per map; O(1) auxiliary map space, plus O(r) output for r matching starts. No temporary length-k substring is created. For a growing alphabet with A distinct keys, full-map comparisons can cost O(A) per window, so do not claim alphabet-independent linear time. Tracking changed equality contributions can avoid full comparisons (L11), but may not be faster for a tiny fixed alphabet. To return only a match count, replace the result list with an integer.

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

Plain words: for finite nonnegative prices, choose at most one buy and a later sell, returning zero when no profitable transaction exists. This is a running-minimum prefix invariant, not a fixed-size sliding window: no oldest price expires. Empty or singleton input returns zero.

def maxProfit(prices):
    lowest = float('inf')         # cheapest price seen so far (left edge candidate)
    best = 0
    for price in prices:          # right edge sweeps forward
        best = max(best, price - lowest)  # buy must precede this sale
        lowest = min(lowest, price)       # retain today's price for future sales
    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

Decision: Answer 'aggregate over every size-k window' efficiently.

Name: Naive recompute per window

Gain: Trivial to write; obviously correct.

Cost: Θ(k(n−k+1)) element visits, potentially excessive; this is not a universal timing claim.

Pick: Only for tiny inputs or a first sanity pass before optimising.

Name: Incremental sliding window

Gain: O(n) time and O(1) auxiliary state for bounded numeric sum/boolean-count scans over an existing indexable input. A frequency map and a live stream’s expiration buffer have separate storage costs.

Cost: Needs a decomposable aggregate; min/max don't qualify directly.

Pick: The default whenever the aggregate has a cheap inverse (sum, count, vowel-count).

Name: Prefix sums

Gain: O(1) for the sum of one specified range of any length after O(n) setup; not O(1) for maximizing over all ranges of that length.

Cost: O(n) extra memory; only for sums, not general aggregates.

Pick: When k varies across many range-sum queries (L12).

Verdict: Incremental window is the default for a single fixed k. Switch to prefix sums when k varies, and to a monotonic deque when the aggregate is a max/min.

Where this shows up

A fixed-count simple moving average uses the last k samples’ sum divided by k once the window is full. A forward-only stream must retain the outgoing samples, commonly in an O(k) ring buffer; the array algorithm’s O(1) auxiliary-space claim assumes those values are still indexable in the input. A time-duration window is a different contract: one arrival can expire many old events, out-of-order arrivals need a policy, and retained state depends on arrival rate. Floating-point accumulation may also need periodic recomputation or a numerical-error strategy.

Checkpoint

You can now…

• Explain why adjacent size-k windows differ by exactly two elements.

• Write the add-entering / drop-leaving update from a blank file.

• State that the entering index is right and the leaving index is right − k.

• Maintain a live Counter over a fixed window and keep it clean.

• Explain why one running maximum is insufficient on expiration and why a deque is one suitable replacement.

• Choose between incremental window and prefix sums based on whether k varies.

Quiz

Self-check (answer follows each question).

Recall check

Q: In the fixed-window sum loop, which index enters and which leaves on each step?

A: right enters; right − k leaves.

Q: Why is naive per-window recompute O(n·k) rather than O(n)?

A: Each of ~n windows redoes k work, rescanning the k−1 elements shared with the previous window.

Q: In the Counter variant, why delete keys whose count hits zero?

A: Cleanup makes len(win) count live distinct characters and bounds stale-key storage. It is not needed for equality on Python 3.10+, where missing counts compare as zero; Counter(a=1)==Counter(a=1,b=0) is True.

Q: Why can't you maintain a window MAXIMUM with a single running variable?

A: The outgoing maximum does not reveal the next maximum. A monotonic deque retains candidates and gives amortized O(1) updates; a heap or other structure can also solve the problem with different costs.

Q: How do you turn 'max window sum' into 'max window average'?

A: Track the max sum with the incremental window, then divide by k once at the end (k is constant).

Q: ★ Stretch: which aggregates ARE O(1)-updatable in a sliding window, and what's the property that makes them so?

A: Bounded integer sum, predicate count and XOR have constant-cost updates in the stated model. For a group operation, inverse removal must respect order: new = inverse(leaving) · old · entering when old is the left-to-right product. Zero has no multiplicative inverse; a product window needs extra zero-count logic and appropriate arithmetic, whose bit cost may grow. Max/min lack an inverse, so a single aggregate is insufficient; that does not make a deque the only possible structure.

Stretch: true

Practice queue

+7d / +21d are optional elapsed-day review suggestions.

• Maximum Average Subarray I (643) — Easy · the canonical fixed window · +7d anchor.
• Best Time to Buy and Sell Stock (121) — Easy · contrast a running-min prefix with a fixed 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.

Corrective source notes

• collections — Container datatypes — Python 3.14.8 documentation — Counter equality in Python 3.10+ treats missing keys as zero counts. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.