Problem
Given an integer array nums consisting of n elements and an integer k, return the maximum average value of any contiguous subarray of length k.Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [1,12,-5,-6,50,3]
k = 4 Output
12.75 Solution
This solution uses a Sliding Window approach to efficiently calculate the sum of every contiguous subarray of length k.First, the sum of the initial window is calculated. As the window slides one position to the right, the new element entering the window is added to the sum, and the element leaving the window is subtracted.
This updates the window sum in
O(1) time without recomputing it from scratch. The maximum window sum encountered during the traversal is maintained. Finally, the maximum average is obtained by dividing the maximum window sum by k.
public double findMaxAverage(int[] nums, int k) {
int sum = 0;
// Calculate the sum of the first window.
for (int i = 0; i < k; i++) {
sum += nums[i];
}
int max = sum;
// Slide the window one element at a time.
for (int i = k; i < nums.length; i++) {
// Add the new element entering the window.
sum += nums[i];
// Remove the element leaving the window.
sum -= nums[i - k];
// Update the maximum window sum.
max = Math.max(max, sum);
}
return (double) max / k;
}
Complexity
The algorithm calculates the first window once and then slides the window across the array. Each element is added to and removed from the window at most once, resulting in a linear time complexity ofO(n). The algorithm uses only a few variables regardless of the input size, so the extra space complexity is
O(1).