Maximum Average Subarray I

Problem

You are given an integer array nums and an integer k. Among all contiguous subarrays of exactly length k, find the one with the largest average value and return that average as a float.

Answers within 10^-5 of the true value are accepted, so ordinary floating-point division is fine.

Examples

• nums = [1, 12, -5, -6, 50, 3], k = 4 → 12.75 — the window [12, -5, -6, 50] sums to 51, and 51 / 4 = 12.75.
• nums = [5], k = 1 → 5.0 — the only window is the single element.
• nums = [-1, -2, -3], k = 2 → -1.5 — with all-negative input the best window is [-1, -2]; the answer can be negative.

Constraints

• 1 <= k <= len(nums) <= 10^5
• -10^4 <= nums[i] <= 10^4

Recomputing each window’s sum from scratch costs O(n·k) — about 10^10 operations in the worst case. The expected solution reuses work between adjacent windows and runs in O(n).

Think about it first

TL;DR

Fixed-size sliding window with an O(1) sum update — O(n) time, O(1) space.

Approach 1 — Brute force

For every start index, sum the k elements of that window.

def findMaxAverage(nums: list[int], k: int) -> float:
    best = float("-inf")
    for i in range(len(nums) - k + 1):
        window_sum = sum(nums[i:i + k])
        best = max(best, window_sum)
    return best / k

Complexity: O(n·k) time, O(k) space for the slices. With n = 10^5 and k near n/2, that’s on the order of 10^9–10^10 additions — far too slow.

Approach 2 — Sliding window sum

The insight: adjacent windows share k - 1 elements. Sliding the window one step right changes the sum by exactly +nums[entering] - nums[leaving], so after paying O(k) once for the first window, every subsequent window costs O(1). (Maximizing the average is the same as maximizing the sum, since k is constant.)

def findMaxAverage(nums: list[int], k: int) -> float:
    window_sum = sum(nums[:k])
    best = window_sum
    for right in range(k, len(nums)):
        window_sum += nums[right] - nums[right - k]
        best = max(best, window_sum)
    return best / k

Walkthrough on nums = [1, 12, -5, -6, 50, 3], k = 4:

Return 51 / 4 = 12.75.

Complexity: O(n) time, O(1) extra space.

Approach 2b — Prefix sums (same complexity, different tool)

The insight: any window sum is a difference of two prefix sums: sum(nums[i:i+k]) = prefix[i+k] - prefix[i]. This costs O(n) extra space here, but generalizes to problems where windows are not visited in sliding order (random ranges, binary search over lengths).

from itertools import accumulate

def findMaxAverage(nums: list[int], k: int) -> float:
    prefix = [0] + list(accumulate(nums))
    best = max(prefix[i + k] - prefix[i] for i in range(len(nums) - k + 1))
    return best / k

Complexity: O(n) time, O(n) space. Prefer the sliding window here; prefix sums are the tool for the non-sliding variants.

Common pitfalls

• Initializing best = 0. With all-negative arrays ([-1, -2, -3], k = 2) the true answer is negative; seed best with the first window’s sum (or -inf), never 0.
• Comparing averages instead of sums. Dividing inside the loop invites needless float error and work; since k is fixed, compare integer sums and divide once at the end.
• Off-by-one on the leaving element. When right enters, the element leaving is nums[right - k] — not right - k + 1 or right - k - 1. Check it on a tiny example (k = 1: entering and leaving indices must differ by exactly k).
• Fixed vs. variable: this window never grows or shrinks — there is no while loop. A fixed-k problem needs no shrink logic.

Pattern takeaway

This is the fixed-size sliding window: when consecutive windows overlap in all but one element at each end, maintain the aggregate incrementally (+entering, -leaving) instead of recomputing it. Any aggregate that supports O(1) insert and remove (sum, count of a class of elements, hash of counts) turns an O(n·k) rescan into an O(n) slide.