You are given an integer array nums consisting of n elements, and an integer k.
Find a contiguous subarray whose length is greater than or equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.
Example 1:
Input: nums = [1,12,-5,-6,50,3], k = 4 Output: 12.75000 Explanation: - When the length is 4, averages are [0.5, 12.75, 10.5] and the maximum average is 12.75 - When the length is 5, averages are [10.4, 10.8] and the maximum average is 10.8 - When the length is 6, averages are [9.16667] and the maximum average is 9.16667 The maximum average is when we choose a subarray of length 4 (i.e., the sub array [12, -5, -6, 50]) which has the max average 12.75, so we return 12.75 Note that we do not consider the subarrays of length < 4.
Example 2:
Input: nums = [5], k = 1 Output: 5.00000
Constraints:
n == nums.length1 <= k <= n <= 104-104 <= nums[i] <= 104Problem Overview: Given an integer array nums and an integer k, find the maximum possible average of any contiguous subarray whose length is at least k. The answer must be computed with high precision, which makes direct enumeration inefficient for large arrays.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
Check every possible subarray of length at least k. Use two nested loops to choose a start and end index, then compute the average by iterating through the elements of that subarray. Track the maximum average encountered. This approach demonstrates the problem definition clearly but performs up to O(n^3) operations because each candidate range requires summing its elements again. It becomes infeasible once the array size grows.
Approach 2: Prefix Sum Optimization (O(n^2) time, O(n) space)
Use a prefix sum array where prefix[i] stores the sum of the first i elements. The sum of any subarray [l, r] can then be computed in constant time using prefix[r+1] - prefix[l]. Iterate over all start indices and expand the end index ensuring the length is at least k, computing averages quickly with the prefix array. This removes the inner summation loop and reduces complexity to O(n^2). It is still too slow for large inputs but introduces the key technique of prefix sum.
Approach 3: Binary Search on Answer + Prefix Sum (O(n logR) time, O(n) space)
The key observation: instead of directly searching for the maximum average, binary search the answer. Assume a candidate average mid. Transform the array by subtracting mid from every value. The problem becomes checking whether a subarray of length ≥ k has a sum ≥ 0. If such a subarray exists, the real maximum average is at least mid.
Use prefix sums to track cumulative values after the transformation. While iterating, maintain the minimum prefix sum seen before index i-k. If currentPrefix - minPrefix ≥ 0, a valid subarray exists. This check runs in O(n). Combine it with binary search over the numeric range of possible averages to reach O(n logR). This method relies on concepts from binary search and array processing.
Recommended for interviews: Interviewers expect the binary search on answer approach. Brute force and prefix sum solutions show that you understand the subarray structure, but the optimized solution demonstrates the ability to transform a numeric optimization problem into a feasibility check using binary search and prefix sums.
We note that if the average value of a subarray with length greater than or equal to k is v, then the maximum average number must be greater than or equal to v, otherwise the maximum average number must be less than v. Therefore, we can use binary search to find the maximum average number.
What are the left and right boundaries of binary search? The left boundary l must be the minimum value in the array, and the right boundary r is the maximum value in the array. Next, we binary search the midpoint mid, and judge whether there exists a subarray with length greater than or equal to k whose average value is greater than or equal to mid. If it exists, then we update the left boundary l to mid, otherwise we update the right boundary r to mid. When the difference between the left and right boundaries is less than a very small non-negative number, i.e., r - l < \epsilon, we can get the maximum average number, where \epsilon represents a very small positive number, which can be 10^{-5}.
The key to the problem is how to judge whether the average value of a subarray with length greater than or equal to k is greater than or equal to v.
We assume that in the array nums, there is a subarray with length j, the elements are a_1, a_2, cdots, a_j, and its average value is greater than or equal to v, i.e.,
$
\frac{a_1 + a_2 + cdots + a_j}{j} geq v
Then,
a_1 + a_2 + cdots + a_j geq v times j
That is,
(a_1 - v) + (a_2 - v) + cdots + (a_j - v) geq 0
We can find that if we subtract v from each element in the array nums, the original problem is transformed into a problem of whether the sum of the elements of a subarray with length greater than or equal to k is greater than or equal to 0. We can use a sliding window to solve this problem.
First, we calculate the sum s of the differences between the first k elements and v. If s geq 0, it means that there exists a subarray with length greater than or equal to k whose element sum is greater than or equal to 0.
Otherwise, we continue to traverse the element nums[j]. Suppose the current sum of the differences between the first j elements and v is s_j. Then we can maintain the minimum value mi of the sum of the differences between the prefix sum and v in the range [0,..j-k]. If s_j geq mi exists, it means that there exists a subarray with length greater than or equal to k whose element sum is greater than or equal to 0, and we return true.
Otherwise, we continue to traverse the element nums[j] until the entire array is traversed.
The time complexity is O(n times log M), where n and M are the length of the array nums and the difference between the maximum and minimum values in the array, respectively. The space complexity is O(1)$.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^3) | O(1) | Conceptual understanding of the problem; very small arrays |
| Prefix Sum Optimization | O(n^2) | O(n) | When improving brute force using fast subarray sum queries |
| Binary Search + Prefix Sum | O(n logR) | O(n) | Optimal solution for large arrays and typical interview expectations |
644. Maximum Average Subarray II (Leetcode Hard) • Programming Live with Larry • 664 views views
Watch 1 more video solutions →Practice Maximum Average Subarray II with our built-in code editor and test cases.
Practice on FleetCode