mediumSliding WindowPattern: Sliding Window
Max Average Subarray Solution
Problem Statement
You are given an array of integers `values` and an integer `k`. Find the maximum average value of any contiguous subarray of size `k`.
Examples
Example 1:
Input:values = [1,12,-5,-6,50,3], k = 4
Output:NaN
Explanation: The subarrays of size 4 are:
[1, 12, -5, -6] with average -1.0
[12, -5, -6, 50] with average 12.75
[-5, -6, 50, 3] with average 13.5
The maximum average is 12.75.
Example 2:
Input:values = [5], k = 1
Output:NaN
Explanation: The only subarray of size 1 is [5], with an average of 5.0.
Example 3:
Input:values = [0, 1, 1, 3, 3], k = 4
Output:NaN
Explanation: The subarrays of size 4 are:
[0, 1, 1, 3] with average 1.25
[1, 1, 3, 3] with average 2.0
The maximum average is 2.0.
Constraints
- 1 <= k <= values.length <= 10^5
- -10^4 <= values[i] <= 10^4
- k is always positive.
Time: O(n) Space: O(1)
Use a sliding window approach. Calculate the sum of the first `k` elements. Then, slide the window one element at a time, updating the sum by subtracting the element that leaves the window and adding the element that enters the window. Maintain the maximum sum encountered and compute the average at the end.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def find_max_average(values, k):
if not values or k <= 0 or k > len(values):
return float('nan')
current_sum = sum(values[:k])
max_sum = current_sum
for i in range(k, len(values)):
current_sum = current_sum - values[i - k] + values[i]
max_sum = max(max_sum, current_sum)
return max_sum / k