🎨Now live: Try our Free AI Image Generation Feature

Description
The problem is to find the maximum average of any subarray of a given length k
in an array. The subarray must be contiguous, and you need to return the maximum possible average value of such subarrays.
Intuition
The key insight is that by maintaining a sliding window sum of length k
, we can efficiently calculate the sum of each subarray of length k
and then compute the average. By updating this sum as we slide the window across the array, we avoid recalculating the sum from scratch, which improves the efficiency.
Approach
- Initialize: Calculate the sum of the first
k
elements. This will serve as the starting point for our sliding window. - Sliding Window: Slide the window across the array by one element at a time, updating the sum by subtracting the element that’s left behind and adding the new element that enters the window.
- Calculate Average: For each window position, calculate the average and update the maximum average found so far.
- Return Result: After processing the entire array, return the maximum average found.
Complexity
Time Complexity:
O(n)
, where n
is the number of elements in the array. This is because we only pass through the array once.
Space Complexity:
O(1)
, since we are using only a fixed amount of extra space for variables, regardless of the input size.
Code
C++
class Solution {
public:
double findMaxAverage(vector& nums, int k) {
double sum = accumulate(nums.begin(), nums.begin() + k, 0);
double ans = -DBL_MAX;
for (int l = 0, r = l + k - 1; l <= nums.size() - k; l++) {
double avg = sum / k;
ans = max(ans, avg);
sum -= nums[l];
r++;
if (r < nums.size()) {
sum += nums[r];
}
}
return ans;
}
};
Python
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
sum_val = sum(nums[:k])
ans = -float('inf')
for l in range(len(nums) - k + 1):
avg = sum_val / k
ans = max(ans, avg)
if l + k < len(nums):
sum_val -= nums[l]
sum_val += nums[l + k]
return ans
Java
class Solution {
public double findMaxAverage(int[] nums, int k) {
double sum = 0;
for (int i = 0; i < k; i++) {
sum += nums[i];
}
double ans = -Double.MAX_VALUE;
for (int l = 0, r = l + k - 1; l <= nums.length - k; l++) {
double avg = sum / k;
ans = Math.max(ans, avg);
sum -= nums[l];
r++;
if (r < nums.length) {
sum += nums[r];
}
}
return ans;
}
}
JavaScript
const findMaxAverage = function (x, k) {
let sum = x.slice(0, k).reduce((acc, cur) => acc + cur, 0);
let avg,
ans = -Infinity;
for (let l = 0, r = l + k - 1; l <= x.length - k; l++) {
avg = (sum / k).toFixed(5);
sum -= x[l];
r++;
sum += x[r];
ans = Math.max(ans, avg);
}
return ans;
};