Maximum Average Subarray I

Problem

A content recommendation system scores candidate batches using the average quality of a fixed-size window. Given an array of quality scores and a window size k, find the maximum average across all contiguous windows of exactly k elements. The window must be contiguous - you cannot pick the k best scores freely.

Example 1:

Input: nums = [2, 10, -4, -7, 45, 6], k = 4
Output: 11.0
Explanation: the window [10, -4, -7, 45] has the maximum average.

Example 2:

Input: nums = [7], k = 1
Output: 7.0

Example 3:

Input: nums = [1, 5, 0, 3, 2], k = 2
Output: 3.0
Explanation: the window [1, 5] has the maximum average.

Constraints:

• 1 <= k <= n <= 10^4
• -1000 <= nums[i] <= 1000

Solution Breakdown

Approach: Fixed-size sliding window over a running sum.

The naive approach recomputes the sum of every k-element window from scratch, which is O(n * k). The key observation is that consecutive windows overlap in all but two positions: sliding right by one drops the leftmost element and gains a new rightmost one. So instead of resumming, you adjust the running total by a single add and a single subtract per step. Seed window_sum = sum(nums[:k]) for the first window, then for each end from k onward do window_sum += nums[end] - nums[end - k] - the entering element at end joins, the element exactly k positions back at end - k leaves. Track best = max(best, window_sum) after each slide. Because k is constant, the window with the largest sum also has the largest average, so you defer the single division to the end (best / k) rather than dividing every step.

Trace [2, 10, -4, -7, 45, 6] with k=4: the first window [2,10,-4,-7] sums to 1. Sliding to [10,-4,-7,45] adds 45 and removes 2, giving 44 - the max, so the answer is 44/4 = 11.0.

Edge cases: When len(nums) == k the loop body never runs and the seeded window is the answer. All-negative arrays work unchanged - the least-negative window wins.

Complexity: O(n) time, O(1) space - the initial sum is O(k) and each of the n - k slides is O(1); only a running sum and a best tracker are stored.