Given an integer array nums and an integer k, find the contiguous subarray of length exactly k with the largest average, and return that average. Answers within 10^-5 of the true value are accepted.
Example 1
Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75
The window
[12,-5,-6,50] sums to 51, and 51 / 4 = 12.75.Example 2
Input: nums = [5], k = 1
Output: 5.0
Constraints
- 1 <= k <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
Hints
Frequently asked at: Google, Amazon, Zoho
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Summing every window from scratch is O(n * k). Since every window has length k, maximising the average is the same as maximising the sum. Neighbouring windows share k - 1 elements, so the next sum is the previous one plus the entering value minus the leaving value. That gives every window sum in O(1) each and O(n) overall. Divide by k once at the end.
Algorithm
- Compute
sumof the firstkelements and setbest = sum. - For
ifromkton - 1, updatesum += nums[i] - nums[i - k]. - Update
best = max(best, sum). - Return
best / kas a decimal number.
Time:
O(n)Space: O(1)Interview tip: Divide only once at the end, and make sure the division is floating point (in Java,
(double) best / k). The harder follow-up, Maximum Average Subarray II, allows any length of at least k and needs binary search on the answer.class Solution: def findMaxAverage(self, nums: List[int], k: int) -> float: total = sum(nums[:k]) best = total for i in range(k, len(nums)): total += nums[i] - nums[i - k] # slide the window by one best = max(best, total) return best / kCtrl + Enter runs the examples