Problem Overview
LeetCode 643 — Maximum Average Subarray I gives you an integer array nums and an integer k. Your task is to find the contiguous subarray of length exactly k that has the highest average value, then return that average as a double.
The subarray must be contiguous, meaning all k elements must be adjacent in the original array. You cannot pick and choose elements from different positions. The length is fixed at exactly k — not "at most k" or "at least k", which makes this a fixed-size sliding window problem.
The return type is a double (floating-point number), so you must divide the sum by k before returning. The problem guarantees that 1 <= k <= n and that the array has at least one valid window.
- Given: integer array nums of length n, and integer k
- Find: contiguous subarray of length exactly k with the maximum average
- Return: the maximum average as a double (floating-point)
- Constraint: 1 <= k <= n <= 100,000 — O(n^2) is too slow
Fixed-Size Sliding Window
The fixed-size sliding window pattern works by computing the sum of the first k elements as a baseline, then advancing the window one step at a time. At each step you add the new right element entering the window and subtract the old left element leaving the window. The sum updates in O(1) per step.
Track the maximum sum seen across all window positions. Once you have scanned the entire array, divide the maximum sum by k to get the maximum average. This gives O(n) time overall because each element is added once and subtracted once.
The window size never changes throughout the algorithm. You always have exactly k elements in the window. This simplicity is what makes this problem a great entry point to the sliding window family.
Simplest Fixed-Size Window
This is the simplest fixed-size sliding window problem: the window size never changes, so you only track the running sum without any shrink logic. No need to check when to shrink — the window always slides forward by exactly one step.
Why Track Sum Not Average
A common beginner mistake is to divide the sum by k at every window position to get the average, then compare averages. This works but wastes computation — you perform n - k + 1 divisions when only one is needed.
The key insight is that for a fixed k, maximizing the sum is equivalent to maximizing the average. If sumA > sumB, then sumA / k > sumB / k. So you can compare sums throughout the algorithm and convert only the final winner to an average with a single division.
This optimization matters more in tighter time limits and in follow-up problems where the divisor varies per window. Always prefer comparing sums when the window size is constant.
- 1Compute the sum of the first k elements — this is windowSum and maxSum
- 2Slide the window: add nums[i], subtract nums[i - k], update maxSum if windowSum is larger
- 3After scanning all windows, return maxSum / k as a double
Prefix Sum Alternative
An alternative approach uses a prefix sum array. Build prefix where prefix[i] is the sum of the first i elements. The sum of any window [i, i+k) equals prefix[i+k] - prefix[i]. Iterate over all valid starting indices and find the maximum difference with gap k.
This approach runs in O(n) time, matching the sliding window. However it requires O(n) extra space for the prefix array, while the sliding window uses only O(1) extra space by maintaining just the running sum variable.
The prefix sum approach is useful when you need to answer multiple range-sum queries on the same array. For this single-query problem, the sliding window is the preferred solution both in space efficiency and interview elegance.
Prefix Sum vs Sliding Window
The prefix sum approach is correct but allocates an O(n) array. The sliding window achieves the same O(n) time result in O(1) extra space by maintaining only the running sum — no auxiliary array needed. For interviews, the sliding window answer is preferred.
Walk-Through Example
Take nums = [1, 12, -5, -6, 50, 3] and k = 4. There are three windows of size 4: [1,12,-5,-6], [12,-5,-6,50], and [-5,-6,50,3]. We want the one with the largest sum.
Initial window sum: 1 + 12 + (-5) + (-6) = 2. This is our starting maxSum. Slide right: add nums[4] = 50, subtract nums[0] = 1. New sum = 2 + 50 - 1 = 51. maxSum updates to 51. Slide again: add nums[5] = 3, subtract nums[1] = 12. New sum = 51 + 3 - 12 = 42. maxSum stays 51.
The maximum sum is 51 from window [12, -5, -6, 50]. Maximum average = 51 / 4 = 12.75. The algorithm visited every element exactly once and performed one division at the end.
- 1Initial sum = 1 + 12 + (-5) + (-6) = 2, maxSum = 2
- 2Slide: add nums[4]=50, subtract nums[0]=1 → windowSum = 51, maxSum = 51
- 3Slide: add nums[5]=3, subtract nums[1]=12 → windowSum = 42, maxSum stays 51
- 4Return maxSum / k = 51 / 4 = 12.75
Code Walkthrough — Python and Java
In Python: compute the initial windowSum as sum(nums[:k]). Set maxSum = windowSum. Loop i from k to len(nums) - 1: windowSum += nums[i] - nums[i - k]. If windowSum > maxSum, update maxSum. Return maxSum / k. Python 3 division is float by default, so no cast needed.
In Java: compute windowSum in a for loop from 0 to k - 1. Set maxSum = windowSum. Loop i from k to nums.length - 1: windowSum += nums[i] - nums[i - k]. If windowSum > maxSum, set maxSum = windowSum. Return (double) maxSum / k. Both solutions run in O(n) time and O(1) space.
The loop structure is the same in both languages. The only language-specific difference is the float division: Python 3 handles it automatically while Java requires an explicit cast to double before dividing.
Integer Division Pitfall
Divide by k as a float, not integer. In Java use (double)maxSum / k — writing maxSum / k with two ints gives integer division and drops the decimal. In Python 3, division is float by default, but in Python 2 you need float(maxSum) / k. Always verify your return type matches the problem signature.