Maximum Average Subarray I
Problem
Given an integer array nums and an integer k, return the maximum average value of any contiguous subarray of length k.
- 1 ≤ k ≤ nums.length ≤ 10⁵
- −10⁴ ≤ nums[i] ≤ 10⁴
Example
nums = [1,12,-5,-6,50,3], k = 412.75The brute-force approach would check every contiguous subarray of length 4, calculate their sums, and track the maximum. For example, subarrays of length 4 are [1,12,-5,-6], [12,-5,-6,50], [-5,-6,50,3]. Their sums are 2, 51, and 42 respectively. The maximum sum is 51, so the maximum average is 51 / 4 = 12.75. The brute-force approach requires O(n*k) time, which is inefficient for large arrays. The optimal approach uses a sliding window of fixed size k. It starts by summing the first k elements, then slides the window forward by one element at a time, updating the sum by adding the new element and removing the element that falls out of the window. This allows the sum of each subarray of length k to be computed in O(1) time after the initial sum, resulting in an O(n) time complexity. The critical moment is when the window moves from index 0-3 to 1-4: the sum is updated by adding nums[4] and subtracting nums[0], efficiently recalculating the sum without re-summing the entire window.
Approach
Straightforward Solution
A brute-force approach iterates over all subarrays of length k, summing each in O(k) time, resulting in O(n*k) total time. This is too slow for large arrays.
Core Observation
The average of a fixed-length subarray depends solely on the sum of its elements. Calculating sums for all subarrays of length k naively requires O(n*k) time, which is inefficient for large inputs.
Path to Optimal
The key insight is that consecutive subarrays of length k overlap significantly. Instead of recomputing sums from scratch, maintain a running sum of the current window. When the window slides forward by one element, update the sum by adding the new element and subtracting the element that leaves the window. This reduces the per-subarray sum calculation to O(1), yielding an O(n) solution.
Optimal Approach
Initialize the sum of the first k elements. Iterate from index k to the end of the array, updating the running sum by adding the new element and subtracting the element k positions behind. Track the maximum sum encountered. Finally, return the maximum sum divided by k as the maximum average.
Time
O(n)
The algorithm computes the initial sum in O(k) time and then iterates through the array once, updating the sum in O(1) time per step, resulting in O(n) total time.
Space
O(1)
Only a fixed number of variables are used to track sums and indices, regardless of input size, resulting in constant auxiliary space.
Pattern Spotlight
Sliding Window (Fixed-Size Window)
When asked to find a property (sum, average, max) of all contiguous subarrays of fixed length k, use a sliding window to maintain a running sum that updates in O(1) time as the window moves, avoiding redundant summations.
Solution
| 1 | class Solution: |
| 2 | def findMaxAverage(self, nums: List[int], k: int) -> float: |
| 3 | |
| 4 | window_sum = sum(nums[:k]) |
| 5 | max_sum = window_sum |
| 6 | |
| 7 | for right in range(k, len(nums)): |
| 8 | window_sum += nums[right] |
| 9 | window_sum -= nums[right - k] |
| 10 | |
| 11 | max_sum = max(max_sum, window_sum) |
| 12 | |
| 13 | return max_sum / k |
Step-by-Step Solution
Compute Initial Window Sum and Set Maximum
| 4 | window_sum = sum(nums[:k]) |
| 5 | max_sum = window_sum |
Objective
To calculate the sum of the first k elements and initialize the maximum sum tracker.
Key Insight
Starting with the sum of the first window establishes a baseline for comparison. This initial sum represents the first contiguous subarray of length k, and setting max_sum to this value ensures the algorithm correctly tracks the maximum as the window slides.
Interview Quick-Check
Core Logic
Summing the first k elements sets the initial window sum, which is the foundation for the sliding window updates.
State & Boundaries
Initialize max_sum with the first window sum to handle cases where the maximum average is in the initial window.
Slide Window Across Array Updating Running Sum and Maximum
| 7 | for right in range(k, len(nums)): |
| 8 | window_sum += nums[right] |
| 9 | window_sum -= nums[right - k] |
| 11 | max_sum = max(max_sum, window_sum) |
Objective
To iterate through the array from index k onward, updating the running sum by adding the new element and removing the element that falls out of the window, while tracking the maximum sum.
Key Insight
Sliding the window forward by one element at a time and updating the sum in O(1) time leverages the overlap between consecutive subarrays. This efficient update avoids recomputing sums from scratch and ensures the algorithm runs in linear time. Tracking the maximum sum during this process guarantees the correct maximum average is found.
Interview Quick-Check
Core Logic
Update the running sum by adding the new element entering the window and subtracting the element leaving it, maintaining the sum of the current window.
State & Boundaries
Iterate from index k to the end, ensuring all subarrays of length k are considered exactly once.
Common Pitfalls & Bugs
Forgetting to subtract the element that leaves the window leads to incorrect sums and results.
Complexity
This approach reduces the time complexity from O(n*k) to O(n) by avoiding redundant summations.
Calculate and Return Maximum Average
| 13 | return max_sum / k |
Objective
To compute the maximum average by dividing the maximum sum by k and return the result.
Key Insight
Since the maximum sum corresponds to the subarray with the highest total, dividing by the fixed window size k yields the maximum average. Returning this value completes the problem's requirement.
Interview Quick-Check
Core Logic
Divide the maximum sum by k to convert the sum into the average value for the subarray.
Line Analysis
This solution has 1 Critical line interviewers watch for.
window_sum -= nums[right - k]Subtract the element leaving the sliding window from the running sum.
Removing the element that falls out of the window keeps the running sum accurate for the current window, preventing accumulation of outdated values.
window_sum = sum(nums[:k])Calculate the sum of the first k elements to initialize the sliding window.
Computing the initial window sum provides the baseline for all subsequent window sums and is necessary to start the sliding window process.
window_sum += nums[right]Add the new element entering the sliding window to the running sum.
Adding the new element updates the window sum to include the latest element, maintaining the correct sum for the current window.
max_sum = max(max_sum, window_sum)Update max_sum if the current window sum is greater.
Tracking the maximum sum ensures the algorithm identifies the subarray with the highest total, which corresponds to the maximum average.
max_sum = window_sumInitialize max_sum with the initial window sum.
Setting max_sum to the first window sum ensures the algorithm correctly tracks the maximum sum found so far, including the initial window.
return max_sum / kReturn the maximum average by dividing max_sum by k.
Dividing the maximum sum by the fixed window size k converts the sum into the average, which is the required output.
for right in range(k, len(nums)):Iterate over the array starting from index k to slide the window.
This loop moves the sliding window forward one element at a time, ensuring all contiguous subarrays of length k are considered.
Test Your Understanding
Why is it more efficient to update the running sum by adding the new element and subtracting the old element rather than recomputing the sum for each subarray?
Because consecutive subarrays of length k overlap by k-1 elements, updating the sum by adding the new element and subtracting the element that leaves the window avoids recomputing the entire sum, reducing the time per subarray from O(k) to O(1) and thus improving overall time complexity from O(n*k) to O(n).
Related Problems
Sliding Window pattern
Don't just read it. Drill it.
Reconstruct Maximum Average Subarray I from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Maximum Average Subarray I drill