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.
Open on LeetCode ↗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.
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
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.
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.
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.
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.