Maximum Average Subarray I
Easy · Sliding Window · Array · Sliding Window
Problem
You are given an integer array nums of length n and an integer k.
Among all contiguous subarrays of length exactly k, find the one with the greatest average and return that average. Answers within 10^-5 of the true value are accepted.
Examples
Input: nums = [2,8,-4,6,10], k = 2 Output: 8.0
The windows of length 2 average 5, 2, 1 and 8, so the best one is [6,10].
Input: nums = [-3], k = 1 Output: -3.0
The only window is [-3], and its average is -3.
Input: nums = [1,12,-5,-6,50,3], k = 4 Output: 12.75
The windows of length 4 sum to 2, 51 and 42, so the best average is 51 / 4 = 12.75.
Constraints
- 1 <= k <= n <= 10^5
- -10^4 <= nums[i] <= 10^4
Approaches
- Sum every window from scratch — time O(n · k), space O(1)
Follow-up
What if the window may be any length of at least k? Then the lengths differ and the largest sum is no longer the largest average. Binary search on the answer: an average of at least x exists exactly when, after subtracting x from every value, some subarray of length at least k has a non-negative sum, which prefix sums and a running minimum check in O(n).
Related problems
Start free on Cariara · Coding problems · System design studio
