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.

Input: nums = [1, 12, -5, -6, 50, 3], k = 4   → 12.75   (window [12, -5, -6, 50])
Input: nums = [5],                      k = 1   → 5.0
Input: nums = [0, 4, 0, 3, 2],          k = 2   → 2.5    (window [3, 2])

Solution

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 [1, 12, -5, -6, 50, 3] with k=4: the first window [1,12,-5,-6] sums to 2. Sliding to [12,-5,-6,50] adds 50 and removes 1, giving 51 - the max, so the answer is 51/4 = 12.75.

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.