Maximum Average Subarray: Fixed Size Sliding Window Basics

"Maximum Average Subarray I" is a Easy-level staple in Google, Amazon, Bloomberg loops, and it is a textbook fit for the Sliding Window pattern — one of the nine patterns that cover the bulk of what FAANG coding interviews actually test. Part 1 of 11 in the Sliding Window arc.

The Problem

Given an integer array nums and an integer k, find the contiguous subarray of length exactly k with the maximum average, and return that average. The naive recomputation of each window's sum costs O(n·k); the interviewer wants O(n).

Input:  nums = [1, 12, -5, -6, 50, 3], k = 4
Output: 12.75
Best window is [12, -5, -6, 50] with sum 51 and average 12.75.

Recognizing the Sliding Window Pattern

Sliding window maintains a contiguous range over an array or string and slides its boundaries instead of recomputing from scratch. Fixed-size windows update a running aggregate in O(1) per step; variable-size windows grow the right edge and shrink the left only when a constraint breaks. Any problem asking about the best contiguous subarray or substring under a constraint should trigger this pattern.

Fixed length k plus a decomposable aggregate (a sum) is the textbook fixed-window setup. Adjacent windows differ by exactly two elements — one enters, one leaves — so each slide is a subtraction and an addition, not a re-scan.

The Approach

Compute the sum of the first k elements. Then slide: add nums[i], subtract nums[i - k], compare against the best. Track the best sum and divide once at the end — fewer float operations and no accumulated error.

This template — seed the first window, then slide with an O(1) update — is the foundation the rest of this arc builds on.

Python Solution

def find_max_average(nums: list[int], k: int) -> float:
    """Maximum average over all contiguous subarrays of length k."""
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best / k

Complexity

• Time: O(n) — one seed pass over k elements, then one O(1) update per slide
• Space: O(1) — a running sum and a best value

Interview Tips and Follow-Ups

• Initialize best from the first real window, not negative infinity converted from habit — all-negative arrays are the planted edge case.
• Follow-up: max sum of any window of size at most k — that shifts you to a variable window or prefix sums; say which and why.
• Same template answers 'max sum', 'min sum', 'count of windows with property X' — name the family, not just this instance.

That wraps part 1 of the Sliding Window arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.