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
PreviewThe 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…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewInitialize 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…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
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
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.
Calculate and Return Maximum Average
To compute the maximum average by dividing the maximum sum by k and return the result.
2 more steps with full analysis available on Pro.
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.
Full line-by-line criticality + rationale for all 7 lines available on Pro.
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?
See the answer with Pro.
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