Maximum Average Subarray I
Last Updated: March 21, 2026
Understanding the Problem
We need to find a window of exactly k consecutive elements that gives us the largest possible average. Since the denominator k is fixed for all windows, the subarray with the maximum sum will also have the maximum average. That observation simplifies things: instead of dividing every window's sum by k during comparison, we can just track the maximum sum and divide once at the end.
The question boils down to: what is the most efficient way to compute the sum of every contiguous subarray of length k?
Key Constraints:
1 <= k <= n <= 10^5→ With up to 100,000 elements, an O(n^2) brute force might be tight but an O(n) solution is ideal.-10^4 <= nums[i] <= 10^4→ Elements can be negative, so we cannot skip any window assuming it will be worse.kcan equaln→ There might be only one valid window (the entire array).
Approach 1: Brute Force
Intuition
The most straightforward way to solve this is to check every possible window of size k. For each starting index i, sum up the k elements from i to i + k - 1, and keep track of the largest sum we find.
This mirrors how you might solve it by hand: slide your finger across the array, stopping at each position to add up the next k numbers, and remember which group had the biggest total.
Algorithm
- Initialize
maxSumto negative infinity. - For each starting index
ifrom0ton - k: - Compute the sum of elements from index
itoi + k - 1. - If this sum exceeds
maxSum, updatemaxSum. - Return
maxSum / kas the maximum average.
Example Walkthrough
Code
- Time Complexity: O(n * k). For each of the
n - k + 1starting positions, we sum upkelements. In the worst case whenkis close ton, this approaches O(n^2). - Space Complexity: O(1). We only use a couple of variables to track the current and maximum sums.
For each window position, we recompute the entire sum from scratch. But consecutive windows overlap in k - 1 elements. What if we reused the previous window's sum and just adjusted for the one element that left and the one that entered?
Approach 2: Sliding Window (Optimal)
Intuition
Here is the key observation: when we move the window one position to the right, we lose the leftmost element and gain a new element on the right. Instead of recalculating the entire sum, we can just subtract the element that dropped off and add the new one that came in.
This is the classic fixed-size sliding window pattern. Compute the sum of the first window once, then "slide" it across the array with a single addition and subtraction per step.
The sliding window exploits the overlap between consecutive windows. Any two adjacent windows of size k share k - 1 elements. Recomputing the sum from scratch ignores this overlap, but the sliding approach leverages it by maintaining a running total and making only incremental updates.
Mathematically, if S(i) is the sum of the window starting at index i, then S(i+1) = S(i) - nums[i] + nums[i+k]. This recurrence lets us compute each new window sum in O(1) instead of O(k).
Algorithm
- Compute the sum of the first
kelements. Call itwindowSum. - Set
maxSum = windowSum. - For each index
ifromkton - 1: - Add
nums[i]towindowSum(new element entering the window). - Subtract
nums[i - k]fromwindowSum(old element leaving the window). - Update
maxSumifwindowSumis larger. - Return
maxSum / k.
Example Walkthrough
Code
- Time Complexity: O(n). We make one pass to compute the initial window sum (O(k)) and one pass to slide across the rest of the array (O(n - k)). Together, that is O(n).
- Space Complexity: O(1). We only use two integer variables (
windowSumandmaxSum) regardless of input size.