Sliding Window — Maximum Average Subarray I
↗ LeetCode: Maximum Average Subarray I · Easy · pattern chapter →
Return the max average of any contiguous subarray of length exactly k.
Example 1 — nums=[1,12,-5,-6,50,3], k=4 → 12.75Example 2 — nums=[5], k=1 → 5.0Example 3 — nums=[-1], k=1 → -1.0
Constraints — 1 ≤ k ≤ n ≤ 10⁵. Brute per-window sum is O(nk) — at n=k=10⁵ that's 10¹⁰ ops (~5 min). Sliding is O(n).
⏱️Interview timer00:00
Approach 1 — Brute per-window sum
Intuition. For each window start, sum k items. Track max.
double findMaxAverageBrute(int[] nums, int k) {
int best = Integer.MIN_VALUE;
for (int i = 0; i + k <= nums.length; i++) {
int sum = 0;
for (int j = i; j < i + k; j++) sum += nums[j];
best = Math.max(best, sum);
}
return best / (double) k;
}2
3
4
5
6
7
8
9
Complexity — Time O(nk); Space O(1). TLE at 10⁵. In an interview say "add-in, drop-out sliding sum → O(n)."
Approach 2 — Fixed-window running sum (canonical)
Insight. Consecutive windows share k-1 items. Pre-sum once; slide with one add + one subtract per step.
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];
best = Math.max(best, sum);
}
return best / (double) k;
}2
3
4
5
6
7
8
9
10
Complexity — Time O(n); Space O(1). Say aloud in an interview: "canonical fixed-window slide — same template as Diet Plan Performance and Contains Duplicate III."
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Per-window sum brute | O(nk) | O(1) | Reference; TLE at 10⁵ |
| Fixed window slide | O(n) | O(1) | Canonical |
When to use which
- Fixed size k, sum-based metric → sliding sum.
- Variable size → constrained window (see Minimum Size Subarray Sum).
- Max avg with size ≥ k → binary search on answer.