35. Maximum Average Subarray I
🔗 LeetCode Problem: 643. Maximum Average Subarray I
📊 Difficulty: Easy
🏷️ Topics: Array, Sliding Window
Problem Statement
You are given an integer array nums consisting of n elements, and an integer k.
Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10^-5 will be accepted.
Example 1:
Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75
Example 2:
Input: nums = [5], k = 1
Output: 5.00000
Constraints:
- n == nums.length
- 1 <= k <= n <= 10^5
- -10^4 <= nums[i] <= 10^4
🎨 Visual Understanding
The Problem Visualized
nums = [1, 12, -5, -6, 50, 3], k = 4
All subarrays of length 4:
[1, 12, -5, -6] → sum = 2, avg = 0.5
[12, -5, -6, 50] → sum = 51, avg = 12.75 ✓ (maximum)
[-5, -6, 50, 3] → sum = 42, avg = 10.5
Answer: 12.75
Key Observation: Fixed Window Size
Unlike "Longest Substring Without Repeating Characters",
this problem has a FIXED window size k.
Window slides one position at a time:
[1, 12, -5, -6], 50, 3
↓
1, [12, -5, -6, 50], 3
↓
1, 12, [-5, -6, 50, 3]
Each step:
- Remove element going out (left side)
- Add element coming in (right side)
- Update sum efficiently
Sliding Window Advantage
Brute Force:
For each window, calculate sum from scratch
Time: O(n × k)
Sliding Window:
Maintain running sum
- Remove nums[i-1] (element leaving window)
- Add nums[i+k-1] (element entering window)
Time: O(n)
Example:
Window 1: [1, 12, -5, -6] → sum = 2
Window 2: [12, -5, -6, 50]
Remove 1, Add 50
sum = 2 - 1 + 50 = 51 ✓
Much faster than recalculating 12 + (-5) + (-6) + 50
🎯 Approach 1: Brute Force
The Most Natural Thinking 💭
Core Logic:
Calculate sum for each window of size k:
1. For each starting position i (from 0 to n-k)
2. Calculate sum of elements from i to i+k-1
3. Track maximum sum
4. Return maximum sum / k
Why This Works: - Checks all possible windows - Guaranteed to find maximum - Easy to understand
Why This Fails Requirements: - Time complexity O(n × k) - Recalculates sum for overlapping windows - Wasteful for large k - Not optimal for interviews
Implementation
public double findMaxAverage(int[] nums, int k) {
int n = nums.length;
double maxAvg = Double.NEGATIVE_INFINITY;
// Try each window of size k
for (int i = 0; i <= n - k; i++) {
// Calculate sum for current window
int sum = 0;
for (int j = i; j < i + k; j++) {
sum += nums[j];
}
// Calculate average and update maximum
double avg = (double) sum / k;
maxAvg = Math.max(maxAvg, avg);
}
return maxAvg;
}
⏰ Time: O(n × k) - n-k+1 windows, each calculated in O(k)
💾 Space: O(1) - only variables
✅ Approach 2: Sliding Window (Optimal)
The Breakthrough Insight 💡
Core Logic:
Use sliding window to maintain running sum:
1. Calculate sum of first k elements (initial window)
2. Slide window one position at a time:
- Remove element leaving window (left)
- Add element entering window (right)
- Update sum: sum = sum - nums[left] + nums[right]
3. Track maximum sum
4. Return maximum sum / k
Key insight: Reuse previous sum instead of recalculating
Visual Explanation:
nums = [1, 12, -5, -6, 50, 3], k = 4
Step 1: Initial window
[1, 12, -5, -6]
sum = 1 + 12 + (-5) + (-6) = 2
maxSum = 2
Step 2: Slide window right
1, [12, -5, -6, 50]
↑ ↑
remove 1 add 50
sum = 2 - 1 + 50 = 51
maxSum = 51
Step 3: Slide window right
1, 12, [-5, -6, 50, 3]
↑ ↑
remove 12 add 3
sum = 51 - 12 + 3 = 42
maxSum = 51 (no update)
Final: maxSum / k = 51 / 4 = 12.75
Why This Works:
Adjacent windows share k-1 elements:
Window i: [a, b, c, d]
Window i+1: [b, c, d, e]
Shared: b, c, d
Instead of: sum = b + c + d + e
We compute: sum = (a + b + c + d) - a + e
This reuses the previous sum!
Time: O(1) per window instead of O(k)
Implementation
public double findMaxAverage(int[] nums, int k) {
int n = nums.length;
// Calculate sum of first window
int sum = 0;
for (int i = 0; i < k; i++) {
sum += nums[i];
}
int maxSum = sum;
// Slide window from position k to n-1
for (int i = k; i < n; i++) {
// Remove element leaving window, add element entering
sum = sum - nums[i - k] + nums[i];
maxSum = Math.max(maxSum, sum);
}
// Return maximum average
return (double) maxSum / k;
}
⏰ Time: O(n) - O(k) for initial window + O(n-k) for sliding
💾 Space: O(1) - only variables
🔍 Step-by-Step Execution
Example: nums = [1, 12, -5, -6, 50, 3], k = 4
Initial State:
═══════════════════════════════════════════════════════════════════
nums = [1, 12, -5, -6, 50, 3]
k = 4
Step 1: Calculate initial window sum
═══════════════════════════════════════════════════════════════════
Window: [1, 12, -5, -6]
i=0 i=1 i=2 i=3
sum = 0
sum += nums[0] = 0 + 1 = 1
sum += nums[1] = 1 + 12 = 13
sum += nums[2] = 13 + (-5) = 8
sum += nums[3] = 8 + (-6) = 2
sum = 2
maxSum = 2
Step 2: Slide window (i = 4)
═══════════════════════════════════════════════════════════════════
Old window: [1, 12, -5, -6]
New window: [12, -5, -6, 50]
Remove nums[i-k] = nums[4-4] = nums[0] = 1
Add nums[i] = nums[4] = 50
sum = sum - nums[0] + nums[4]
sum = 2 - 1 + 50 = 51
maxSum = max(2, 51) = 51
Step 3: Slide window (i = 5)
═══════════════════════════════════════════════════════════════════
Old window: [12, -5, -6, 50]
New window: [-5, -6, 50, 3]
Remove nums[i-k] = nums[5-4] = nums[1] = 12
Add nums[i] = nums[5] = 3
sum = sum - nums[1] + nums[5]
sum = 51 - 12 + 3 = 42
maxSum = max(51, 42) = 51 (no change)
Step 4: Calculate result
═══════════════════════════════════════════════════════════════════
maxAverage = maxSum / k
maxAverage = 51 / 4 = 12.75
═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: 12.75
═══════════════════════════════════════════════════════════════════
Another Example: nums = [0, 4, 0, 3, 2], k = 1
k = 1 means each element is its own window
Step 1: Initial window
Window: [0]
sum = 0
maxSum = 0
Step 2: i = 1
Window: [4]
sum = 0 - 0 + 4 = 4
maxSum = 4
Step 3: i = 2
Window: [0]
sum = 4 - 4 + 0 = 0
maxSum = 4
Step 4: i = 3
Window: [3]
sum = 0 - 0 + 3 = 3
maxSum = 4
Step 5: i = 4
Window: [2]
sum = 3 - 3 + 2 = 2
maxSum = 4
Result: 4 / 1 = 4.0
🔍 Edge Cases
Case 1: Single element array
Input: nums = [5], k = 1
Output: 5.00000
Explanation: Only one window possible
Case 2: Window size equals array size
Input: nums = [1, 2, 3, 4], k = 4
Output: 2.50000
Explanation: Only one window (entire array)
Case 3: All negative numbers
Input: nums = [-1, -2, -3, -4], k = 2
Output: -1.50000
Explanation: Maximum is [-1, -2]
Case 4: All positive numbers
Input: nums = [1, 2, 3, 4, 5], k = 3
Output: 4.00000
Explanation: Maximum is [3, 4, 5]
Case 5: Mix of positive and negative
Input: nums = [-1, 5, -3, 2], k = 2
Output: 3.50000
Explanation: Maximum is [5, -3] = 2, or actually [5, -3] is incorrect
Let me recalculate: [-1, 5] = 4, [5, -3] = 2, [-3, 2] = -1
Maximum is [-1, 5] / 2 = 4 / 2 = 2.0
Case 6: Large k
Input: nums = [1, 2, 3, 4, 5], k = 5
Output: 3.00000
Explanation: Only one window (entire array)
Case 7: k = 2
Input: nums = [8, 6, 4, 2], k = 2
Output: 7.00000
Explanation: Maximum is [8, 6]
Case 8: Zero in array
Input: nums = [0, 0, 0, 0], k = 2
Output: 0.00000
Common Mistakes
Mistake 1: Calculating average in the loop
❌ Wrong:
for (int i = k; i < n; i++) {
sum = sum - nums[i - k] + nums[i];
maxAvg = Math.max(maxAvg, (double) sum / k);
}
✓ Right:
for (int i = k; i < n; i++) {
sum = sum - nums[i - k] + nums[i];
maxSum = Math.max(maxSum, sum);
}
return (double) maxSum / k;
Reason: Comparing sums is same as comparing averages, saves divisions
Mistake 2: Wrong initial window calculation
❌ Wrong:
for (int i = 0; i < k - 1; i++) { // Missing last element
sum += nums[i];
}
✓ Right:
for (int i = 0; i < k; i++) {
sum += nums[i];
}
Reason: Need all k elements in initial window
Mistake 3: Wrong sliding index
❌ Wrong:
for (int i = 1; i < n; i++) { // Start from wrong position
sum = sum - nums[i - 1] + nums[i];
}
✓ Right:
for (int i = k; i < n; i++) { // Start from k
sum = sum - nums[i - k] + nums[i];
}
Reason: First window already calculated, start sliding from position k
Mistake 4: Not initializing maxSum correctly
❌ Wrong:
int maxSum = 0; // What if all numbers are negative?
✓ Right:
int maxSum = sum; // Initialize with first window
Reason: First window might be the maximum
Mistake 5: Integer division for average
❌ Wrong:
return maxSum / k; // Integer division
✓ Right:
return (double) maxSum / k; // Cast to double
Reason: Need decimal result
Mistake 6: Wrong window removal
❌ Wrong:
sum = sum - nums[i - 1] + nums[i];
✓ Right:
sum = sum - nums[i - k] + nums[i];
Reason: Remove element k positions back, not previous element
🎯 Key Takeaways
⚡ Algorithm Comparison
Approach 1: Brute Force
Time: O(n × k)
Space: O(1)
Use: Only for understanding
Approach 2: Sliding Window (RECOMMENDED)
Time: O(n)
Space: O(1)
Use: Optimal solution, best for interviews
🔑 The Core Insight
Fixed-Size Sliding Window Pattern:
Key Characteristics:
- Window size is FIXED (k)
- Window slides one position at a time
- Adjacent windows share k-1 elements
Optimization:
Instead of recalculating sum for each window,
reuse previous sum:
sum_new = sum_old - element_leaving + element_entering
Time Savings:
- Brute Force: O(k) per window → O(n × k) total
- Sliding Window: O(1) per window → O(n) total
Formula:
For window ending at position i:
sum[i] = sum[i-1] - nums[i-k] + nums[i]
Where:
- sum[i-1] is previous window sum
- nums[i-k] is element leaving window
- nums[i] is element entering window
🎯 Pattern Recognition
Problem Type: Fixed-Size Subarray with Max/Min Property
Core Pattern: Fixed-Size Sliding Window
When to Apply:
✓ Need to find subarray of FIXED size k
✓ Looking for max/min sum, average, or product
✓ Can maintain running calculation
✓ Want O(n) time complexity
Key Techniques:
→ Calculate initial window (first k elements)
→ Slide window one position at a time
→ Update sum: remove left, add right
→ Track maximum/minimum during sliding
→ Return result (sum, average, etc.)
Template:
1. Calculate sum of first k elements
2. Initialize max/min with first window
3. For i from k to n-1:
- Update sum: sum = sum - nums[i-k] + nums[i]
- Update max/min
4. Return result
Related Problems:
- Maximum Sum of Distinct Subarrays With Length K (LC 2461)
- Sliding Window Maximum (LC 239)
- Minimum Size Subarray Sum (LC 209)
- Maximum Points You Can Obtain from Cards (LC 1423)
🧠 Interview Strategy
Step 1: "Need maximum average of subarray with fixed size k"
Step 2: "Brute force: calculate each window - O(n × k)"
Step 3: "Optimization: sliding window reuses previous sum"
Step 4: "Remove element leaving, add element entering"
Step 5: "O(n) time, O(1) space"
Key Points to Mention:
- Fixed window size (unlike variable-size sliding window)
- Adjacent windows share k-1 elements
- Reuse previous sum for O(1) update
- Track maximum sum, divide by k at end
- O(n) time complexity
- O(1) space complexity
📝 Quick Revision Notes
🎯 Core Concept:
Fixed-size sliding window of size k. Calculate initial window, then slide by removing left element and adding right element. Track maximum sum.
⚡ Quick Implementation:
public double findMaxAverage(int[] a, int k) {
int runningSum = 0;
for(int i = 0; i < k; i++) {
runningSum += a[i];
}
double res = (double)runningSum / k;
for(int i = k; i < a.length; i++) {
runningSum -= a[i - k];
runningSum += a[i];
res = Math.max(res, (double)runningSum / k);
}
return res;
}
🔑 Key Insights:
- Fixed window size: k elements always
- Initial window: Calculate sum of first k elements
- Sliding formula:
sum = sum - nums[i-k] + nums[i] - Start sliding at: i = k (after initial window)
- Remove: nums[i-k] (element k positions back)
- Add: nums[i] (current element)
- Track max: Update maxSum during sliding
- Return: (double) maxSum / k (cast to double)
- Time: O(n) - O(k) initial + O(n-k) sliding
- Space: O(1) - only variables
- Key advantage: Reuse previous sum, O(1) per update
🎪 Memory Aid:
"Calculate FIRST k, then SLIDE: remove LEFT, add RIGHT!"
Think: "Fixed window slides, reuse sum, track max"
Related Patterns
- Maximum Sum of Distinct Subarrays With Length K (LC 2461)
- Sliding Window Maximum (LC 239)
- Minimum Size Subarray Sum (LC 209)
- Maximum Points You Can Obtain from Cards (LC 1423)
Happy practicing! 🎯