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.
- n == nums.length
- 1 <= k <= n <= 10⁵
- -10⁴ <= nums[i] <= 10⁴
Intuition
Maximum average subarray i finds the highest average over any contiguous subarray of exactly length k. The fixed length is what makes this a straightforward sliding window.
The first simplification removes division from the inner loop entirely:
- Every window has the same length k, so comparing sums is equivalent to comparing averages — divide only once, at the end.
That avoids repeated floating-point division and, more importantly, avoids accumulating rounding error across comparisons. Comparing averages directly can misorder two windows whose sums differ by a small amount.
Computing each window's sum from scratch is O(n × k). The window update makes it O(n):
Consecutive windows differ by exactly two elements — one leaves the left, one enters the right. So sum += nums[i] − nums[i − k] maintains the sum in constant time per step.
Build the first window's sum before the loop begins, then slide from index k onward. Starting the slide at index 0 double-counts the initial elements, which is the usual error here.
The maximum sum must be initialised to the first window's sum, not to zero. All values can be negative, in which case every sum is below zero and a zero starting point would be returned as the answer.
The division happens once at the end, and must produce a floating-point result — integer division would truncate the average and fail on nearly every test.
Space stays O(1), since only a running sum and a maximum are held.
Fixed-width window: add the entering element, subtract the leaving one, in one expression. Since the width never changes, maximising the average is the same as maximising the sum — dividing once at the end avoids repeated floating-point work.
Approach
Before reading on: price up what the direct approach costs here, then ask what makes a window invalid, and which pointer should move when it is. Aim for O(n) time and O(1) space.
Compare sums, not averages
Every window has the same length, so sums order identically to averages. Dividing once at the end avoids repeated division and accumulated rounding error.
Build the first window
Sum the first k elements before the loop. This seeds both the running sum and the initial maximum.
Slide with a two-element update
Consecutive windows differ by two elements, so sum += nums[i] - nums[i - k] maintains it in O(1). Start the slide at index k — starting at 0 double-counts.
Initialise the maximum correctly
Set the maximum to the first window's sum, not to zero. With all-negative values, every sum is below zero and a zero start would be returned instead.
Divide once at the end
Convert the best sum to an average with floating-point division. Integer division truncates and fails nearly every test case.
Cost of the scan
Each element enters and leaves the window once, giving O(n) time and O(1) space — a running sum and a maximum, nothing more.
Solution & live demo
Common pitfalls
Dividing inside the loop
best = max(best, window_sum / k)
best_sum = max(best_sum, window_sum) return best_sum / k
With a constant width, the sum and the average are ordered identically, so the division is redundant work — and accumulating floating-point comparisons risks ties resolving inconsistently. Divide once at the end.
Recomputing the window sum each step
window_sum = sum(nums[right - k + 1 : right + 1])
window_sum += nums[right] - nums[right - k]
That's O(nk) and re-adds the k - 1 elements the window already contains. The two-term update is O(1) per position.
Seeding best at zero
best_sum = 0
best_sum = window_sum
Values can be negative, so an all-negative array has a maximum sum below zero and the seed would win. Starting from the first real window is always a valid candidate.
Edge cases
There is only one window, so the initial sum built before the loop is already the answer; the sliding loop simply does not execute.
Sum comparison still correctly finds the least-negative (largest) window sum; no special-casing is needed since comparison works the same regardless of sign.
Each window is a single element; the running sum update degenerates to comparing individual elements, and the answer is simply the maximum element.
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.