Maximum Average Subarray I
Find the highest-average window of fixed length k by sliding a window instead of recomputing sums
Problem Statement
Given an integer array nums and an integer k, find the contiguous subarray of exactly k elements with the maximum average, and return that average.
Input: nums = [1, 12, -5, -6, 50, 3], k = 4
Output: 12.75
Why: the window [12, -5, -6, 50] sums to 51 → 51 / 4 = 12.75
Input: nums = [5], k = 1
Output: 5.00000Intuition
Because k is fixed, the average is just sum / k — and k never changes. So maximising the average is exactly the same as maximising the sum. Divide only once, at the very end.
The naive method walks every starting position and adds up k elements: O(n × k). But look at what happens between two neighbouring windows:
nums = [1, 12, -5, -6, 50, 3], k = 4
window at 0: [ 1, 12, -5, -6] sum = 2
window at 1: [12, -5, -6, 50] sum = 51Almost everything is shared. Only two elements differ.
The key insight
Sliding a fixed window one step right means:
subtract the element that fell off the left, add the element that entered on the right.
Two operations, not k. Every element is added once and removed once across the whole run.
Real-world analogy
A 7-day moving average of your step count. You never re-add all seven days — you drop the oldest day and add today.
Approach
Build the first window
Sum nums[0 … k-1]. This is the only place you pay O(k).
Slide to the end
For each i from k to n-1: window += nums[i] - nums[i - k].
nums[i] is entering the window and nums[i - k] is the one leaving it.
Track the maximum sum, divide once
Return best / k as a floating-point number.
Watch it run
Solution
def find_max_average(nums: list[int], k: int) -> float:
"""Highest average over any contiguous subarray of exactly k elements."""
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k] # add entering, drop leaving
best = max(best, window)
return best / kDo not start `best` at zero
best = 0 is wrong for arrays that are entirely negative — nums = [-1, -2], k = 1 would return 0 instead of -1. Seed best with the first real window, or with negative infinity.
Integer division in Python
51 // 4 is 12, not 12.75. Use a single slash (/) so the result is a float. In TypeScript all numbers are floating point, so / already does the right thing.
Fixed vs. Variable Windows
This is the fixed-size sliding window: the width never changes, so the loop is a simple slide. The other flavour — the variable-size window — grows and shrinks based on a condition (for example "the longest substring with no repeats"), and uses two independent pointers with an inner while loop.
Recognising which kind a problem needs is most of the work:
| Clue in the problem | Window type |
|---|---|
"subarray of size k" | Fixed |
| "longest/shortest subarray such that …" | Variable |
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
- Time —
O(k)to build the first window plusO(n - k)slides, which isO(n)overall. The naive version isO(n × k); atn = 10⁵,k = 10⁴that is a billion operations versus a hundred thousand. - Space — two numbers.
Edge Cases
Related Problems
- Running Sum of 1d Array — prefix sums, the other way to answer range-sum questions fast
- Best Time to Buy and Sell Stock — another single-pass running statistic
- Longest Palindrome — counting inside a pass instead of rescanning