Here’s the question link on LeetCode 643. Maximum Average Subarray I:
https://leetcode.com/problems/maximum-average-subarray-i/description
Contents
Brute Force O(n × k)
The straightforward approach is to calculate the sum of every possible subarray of size k.
For every starting index, I can iterate over the next k elements, calculate their sum, and update the maximum average.
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int n = nums.size();
double ans = -1e9;
for(int i = 0; i <= n - k; i++) {
int sum = 0;
for(int j = i; j < i + k; j++) {
sum += nums[j];
}
ans = max(ans, (double)sum / k);
}
return ans;
}
};
Optimal O(n) – Sliding Window
Wait, we’re calculating almost the same thing again and again.
Think about two consecutive windows:
[1, 12, -5, -6] // sum = 2
[12, -5, -6, 50] // sum = 51
Notice something? Both windows share k-1 elements!
The only difference is:
- The first element leaves the window.
- A new element enters the window.
So instead of calculating the entire sum again, we can simply subtract the element leaving and add the new element.
This is called Sliding Window.
Also, since every window has exactly k elements, maximizing the average is the same as maximizing the sum. We only need to divide by k at the end.
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int n = nums.size();
int sum = 0;
// Calculate the first window
for(int i = 0; i < k; i++) {
sum += nums[i];
}
int maxSum = sum;
// Slide the window
for(int i = k; i < n; i++) {
sum += nums[i] - nums[i-k];
maxSum = max(maxSum, sum);
}
return (double)maxSum / k;
}
};
That’s it; see you in the next one.
643. Maximum Average Subarray I 643. Maximum Average Subarray I 643. Maximum Average Subarray I