Maximum Average Subarray I
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 simplifies the work: instead of dividing every window's sum by k during comparison, 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 does up to 10^10 operations and risks timing out, so an O(n) solution is the target.-10^4 <= nums[i] <= 10^4→ Elements can be negative, so no window can be skipped on the assumption that it will be worse. The maximum possible window sum is10^5 * 10^4 = 10^9, which fits in a 32-bit signed integer.kcan equaln→ There may be only one valid window, the entire array.
Approach 1: Brute Force
Intuition
Check every possible window of size k. For each starting index i, sum the k elements from i to i + k - 1, and keep track of the largest sum found. There are n - k + 1 valid starting positions, and each requires summing k elements.
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, the brute force recomputes the entire sum from scratch, even though consecutive windows overlap in k - 1 elements. The next approach reuses the previous window's sum and adjusts only for the one element that left and the one that entered.
Approach 2: Sliding Window (Optimal)
Intuition
When the window moves one position to the right, it loses the leftmost element and gains a new element on the right. Instead of recalculating the entire sum, subtract the element that dropped off and add the one that came in. This is the fixed-size sliding window pattern: compute the sum of the first window once, then move it across the array with a single addition and subtraction per step.
Let S(i) be the sum of the window starting at index i. The window at i+1 contains the same elements as the window at i, except nums[i] is no longer included and nums[i+k] is now included. So S(i+1) = S(i) - nums[i] + nums[i+k]. This recurrence computes each new window sum in O(1), and it produces the exact same sums the brute force would, so the maximum found is identical.
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.