#643
Maximum Average Subarray I
Easy Fixed window
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Find the contiguous subarray of length k with the largest average and return that average.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the best average of any k neighbours in a row.
Why this works: k is fixed, so best average = best sum ÷ k. Slide: add the new number, subtract the one that left.
Example: [1, 12, -5, -6, 50, 3], k = 4
first window 1+12-5-6 = 2slide: +50 -1 = 51slide: +3 -12 = 42best 51 → 12.75
✦Hints open one at a time
The largest average comes from the largest sum, since k is fixed.
When the window slides, add the new element and subtract the one that left.
↗Approach
Sum the first k elements. Then slide: sum += nums[i] - nums[i - k]. Track the best sum and divide by k at the end.
</>Solution (Java)
class Solution {
public double findMaxAverage(int[] nums, int k) {
int sum = 0;
for (int i = 0; i < k; i++) sum += nums[i];
int best = sum;
for (int i = k; i < nums.length; i++) {
sum += nums[i] - nums[i - k]; // slide by one
best = Math.max(best, sum);
}
return (double) best / k;
}
}!Common mistake
Re-summing all k elements for every window — O(n·k).
Complexity
- Time: O(n).
- Space: O(1).
Topic: Sliding Window
🎬 Episode 10: video coming soon