Find the maximum average of any contiguous subarray of size k.
Compute the sum of the first k elements, then slide the window one step at a time — add the incoming element and subtract the outgoing element. Track the best sum seen and divide by k at the end. One pass, O(n) time, O(1) extra space.
How to think about it
Recognise the pattern
The signal is fixed-size window + aggregate (sum, max, average) over contiguous elements. Any time k is constant and you’re asked for a property of every (or the best) window of that size, the fixed sliding window is the answer. The window moves one step at a time, so consecutive windows overlap in k-1 elements — you never need to recompute them from scratch.
Build the approach step by step
Brute force loops over every starting index i from 0 to n-k, summing nums[i:i+k]. Each sum takes O(k), total is O(n·k).
The insight: consecutive windows of size k differ by exactly one element — the one entering on the right, and the one leaving on the left. So the new window sum is:
window_sum = window_sum + nums[right] - nums[right - k]This is O(1) per step instead of O(k).
Walk through [1, 12, -5, -6, 50, 3], k=4:
- Initial window [1,12,-5,-6]: sum = 2
- Slide: add 50, subtract 1 → sum = 51
- Slide: add 3, subtract 12 → sum = 42
- Best sum = 51, average = 51/4 = 12.75
Complexity
- Time — O(n): one pass across the array after the O(k) initial sum (which is also O(n) in the worst case).
- Space — O(1): just three variables (
window_sum,best,right).