LeetCode #643 Easy

Maximum Average Subarray I

Given an integer array nums and an integer k, find the contiguous subarray of length k with the maximum average, and return that average.

arraysliding-window

Open on LeetCode ↗

02

Intuition

💡

The trap is recomputing the sum of each k-length window from scratch as you slide across the array, which costs O(n * k) since every window re-adds all k of its elements. The window has a fixed width, so instead keep a single running sum: build the first window's sum once, then at every step add the element entering on the right and subtract the element leaving on the left -- O(1) work per slide. The second, quieter trap is comparing averages instead of sums while you scan: dividing by k on every single step adds unnecessary floating point noise and unnecessary division operations for no benefit, since the window width k never changes and dividing by the same constant preserves the ordering. Compare raw sums the whole way through, track the best sum seen, and only divide once at the very end to produce the final average.

03

Approach

1

Build the first window's sum once

Sum the first k elements directly to seed a running total. This is the only place a full k-element sum is ever computed.

2

Slide with add-one-subtract-one

For each subsequent right edge, add nums[right] and subtract nums[right - k] from the running sum. This keeps the sum correct for the new window in O(1) regardless of k.

3

Compare sums, divide once at the end

Track the best sum seen across all windows using plain integer/float comparison, not averages. Only after the scan finishes divide the best sum by k to produce the answer, avoiding repeated division and the floating point drift it can introduce.

04

Solution & live demo

python

▶1class Solution:
▶2    def findMaxAverage(self, nums, k):
▶3        window_sum = sum(nums[:k])
▶4        best_sum = window_sum
▶5        for right in range(k, len(nums)):
▶6            window_sum += nums[right] - nums[right - k]
▶7            best_sum = max(best_sum, window_sum)
▶8        return best_sum / k

05

Edge cases

k equals the length of nums

There is only one window, so the initial sum built before the loop is already the answer; the sliding loop simply does not execute.

All negative numbers

Sum comparison still correctly finds the least-negative (largest) window sum; no special-casing is needed since comparison works the same regardless of sign.

k equal to 1

Each window is a single element; the running sum update degenerates to comparing individual elements, and the answer is simply the maximum element.

Large array with k much smaller than n

The O(n) running-sum approach keeps per-step work constant regardless of k, avoiding the O(n*k) blowup a naive per-window resum would hit.

06

Complexity

Time

O(n)

Space

O(1)

Each element is added once and subtracted once as it enters and leaves the window; no per-window recomputation.