LeetCode 644 - Maximum Average Subarray II
The problem asks us to find the maximum possible average value among all contiguous subarrays whose length is at least k. We are given an integer array nums and an integer k. A subarray is a contiguous portion of the array, meaning the elements must appear consecutively.
Difficulty: 🔴 Hard
Topics: Array, Binary Search, Prefix Sum
Solution
LeetCode 644 - Maximum Average Subarray II
Problem Understanding
The problem asks us to find the maximum possible average value among all contiguous subarrays whose length is at least k.
We are given an integer array nums and an integer k. A subarray is a contiguous portion of the array, meaning the elements must appear consecutively. Unlike simpler sliding window problems where the subarray length is fixed, here the subarray can be any length greater than or equal to k. Our task is to determine the highest average obtainable and return it as a floating-point number.
The result is accepted as long as the error is smaller than 10^-5, which strongly suggests that an exact rational value is unnecessary. This tolerance is a major clue that a binary search on the answer space is likely appropriate.
The constraints also guide the solution design:
1 <= k <= n <= 10^4-10^4 <= nums[i] <= 10^4
Since n can reach 10^4, a brute-force solution that checks every subarray and computes every average directly would be prohibitively expensive. We need something substantially better than quadratic time.
Several important edge cases deserve attention:
First, the array may contain negative numbers. This prevents greedy strategies based solely on positive accumulation. A valid maximum average may come from balancing positive and negative values.
Second, the best subarray may have exactly length k, or it may be significantly longer. We cannot assume a fixed window size.
Third, when n = 1 and k = 1, the answer is simply the only element itself. The algorithm must gracefully handle this smallest input.
Finally, the array may contain all identical values or all negative values. The implementation must still correctly determine the maximum average.
Approaches
Brute Force Approach
A straightforward approach would enumerate every possible subarray whose length is at least k, compute its average, and track the maximum.
We could generate every starting index and every ending index, compute the sum of the subarray, and divide by its length. To avoid recomputing sums repeatedly, prefix sums could reduce each subarray sum computation to O(1).
Even with prefix sums, there are still O(n²) possible subarrays. Since each subarray must be checked, the total time complexity becomes O(n²).
For n = 10^4, this becomes too slow because roughly 10^8 operations may be required in the worst case.
Optimal Approach, Binary Search on the Answer
The key observation is that we are not asked to return the subarray itself, only the maximum average value.
Instead of searching through subarrays directly, we can binary search the answer. Suppose we guess an average mid. The question becomes:
Can we find a subarray of length at least k whose average is at least mid?
If yes, then the true answer is at least mid, so we should search higher.
If no, then mid is too large, and we should search lower.
To test feasibility efficiently, we transform the array:
$$transformed[i] = nums[i] - mid$$
Now the problem becomes determining whether there exists a subarray of length at least k whose sum is non-negative.
Why does this work?
If:
$$\frac{sum(subarray)}{length} \ge mid$$
then:
$$sum(subarray) - mid \cdot length \ge 0$$
which is exactly the sum of the transformed subarray.
We can verify this in linear time using prefix sums and a running minimum prefix value.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Enumerates all valid subarrays using prefix sums |
| Optimal | O(n log R) | O(1) | Binary search on answer space, where R is numeric range |
Here, R represents the precision range between the minimum and maximum values in the array.
Algorithm Walkthrough
Optimal Algorithm
- Initialize the binary search range.
Since the answer must lie between the smallest and largest values in nums, set:
left = min(nums)right = max(nums)
The maximum average cannot be smaller than the minimum element or larger than the maximum element.
2. Define a helper function can_find(guess).
This function determines whether there exists a subarray of length at least k with average at least guess.
3. Transform the running sums.
Instead of explicitly creating a transformed array, compute:
$$nums[i] - guess$$
while iterating.
4. Compute the first window of size k.
Calculate the transformed sum of the first k elements.
If this sum is non-negative, then a valid subarray already exists. 5. Track prefix contributions before the current window.
Maintain:
prefix_sum, cumulative transformed summin_prefix_sum, smallest prefix seen so far
The reason for storing the minimum prefix is that subtracting a smaller prefix maximizes the subarray sum. 6. Iterate through the remaining elements.
For each new position:
- Extend the current transformed sum.
- Update prefix information.
- Check whether:
$$current_sum - min_prefix_sum \ge 0$$
If true, a valid subarray exists. 7. Perform binary search.
If can_find(mid) is true:
- Move left boundary upward.
Otherwise:
- Move right boundary downward.
- Continue until precision is sufficient.
Stop when:
$$right - left < 10^{-5}$$
Return left.
Why it works
The algorithm works because binary search repeatedly narrows the range containing the maximum average. The helper function correctly determines feasibility by converting the average constraint into a subarray sum constraint. By subtracting the guessed average from each number, any subarray with non-negative transformed sum corresponds exactly to a subarray whose average is at least the guess. Since feasibility is monotonic, meaning smaller guesses remain feasible once a larger one is feasible, binary search is valid.
Python Solution
from typing import List
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
def can_find(target_average: float) -> bool:
current_sum = 0.0
for index in range(k):
current_sum += nums[index] - target_average
if current_sum >= 0:
return True
prefix_sum = 0.0
min_prefix_sum = 0.0
for index in range(k, len(nums)):
current_sum += nums[index] - target_average
prefix_sum += nums[index - k] - target_average
min_prefix_sum = min(
min_prefix_sum,
prefix_sum
)
if current_sum - min_prefix_sum >= 0:
return True
return False
left = float(min(nums))
right = float(max(nums))
precision = 1e-5
while right - left > precision:
middle = (left + right) / 2
if can_find(middle):
left = middle
else:
right = middle
return left
The implementation begins by defining the can_find helper function, which determines whether a candidate average is achievable.
Instead of constructing a transformed array explicitly, the function computes nums[i] - target_average on the fly. This reduces memory usage and keeps the implementation concise.
The first k transformed elements are summed immediately because the smallest valid subarray size is k. If this initial transformed sum is already non-negative, then a valid subarray exists.
For longer subarrays, the implementation tracks prefix sums. prefix_sum stores the transformed values that fall outside the current valid window, while min_prefix_sum keeps the smallest prefix encountered. Subtracting the smallest prefix maximizes the possible subarray sum ending at the current position.
Finally, binary search repeatedly narrows the candidate average range until the precision requirement is met.
Go Solution
import "math"
func findMaxAverage(nums []int, k int) float64 {
canFind := func(targetAverage float64) bool {
currentSum := 0.0
for i := 0; i < k; i++ {
currentSum += float64(nums[i]) - targetAverage
}
if currentSum >= 0 {
return true
}
prefixSum := 0.0
minPrefixSum := 0.0
for i := k; i < len(nums); i++ {
currentSum += float64(nums[i]) - targetAverage
prefixSum += float64(nums[i-k]) - targetAverage
minPrefixSum = math.Min(
minPrefixSum,
prefixSum,
)
if currentSum-minPrefixSum >= 0 {
return true
}
}
return false
}
left := float64(nums[0])
right := float64(nums[0])
for _, num := range nums {
value := float64(num)
left = math.Min(left, value)
right = math.Max(right, value)
}
precision := 1e-5
for right-left > precision {
middle := (left + right) / 2
if canFind(middle) {
left = middle
} else {
right = middle
}
}
return left
}
The Go implementation closely mirrors the Python version. Since Go does not automatically convert integers to floating-point values, explicit float64() conversions are necessary whenever arithmetic involves averages.
The implementation uses math.Min and math.Max to compute boundaries and maintain the minimum prefix sum efficiently. Go slices naturally handle iteration, so no special handling for empty arrays is required because the constraints guarantee n >= 1.
Worked Examples
Example 1
Input:
nums = [1,12,-5,-6,50,3]
k = 4
Suppose binary search tests:
guess = 12.75
Transform values implicitly:
| Index | nums[i] | nums[i] - 12.75 |
|---|---|---|
| 0 | 1 | -11.75 |
| 1 | 12 | -0.75 |
| 2 | -5 | -17.75 |
| 3 | -6 | -18.75 |
| 4 | 50 | 37.25 |
| 5 | 3 | -9.75 |
First k = 4 sum:
| Window | Sum |
|---|---|
[1,12,-5,-6] |
-49.00 |
Not valid.
Extend to index 4:
| Variable | Value |
|---|---|
| current_sum | -11.75 |
| prefix_sum | -11.75 |
| min_prefix_sum | -11.75 |
| current_sum - min_prefix_sum | 0 |
Since the result becomes non-negative, a valid subarray exists:
[12, -5, -6, 50]
Average:
$$\frac{12 + (-5) + (-6) + 50}{4} = 12.75$$
Thus 12.75 is feasible.
Example 2
Input:
nums = [5]
k = 1
Binary search boundaries:
left = 5
right = 5
Since the range is already smaller than precision, the algorithm immediately returns:
5.0
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log R) | Each binary search step performs an O(n) feasibility check |
| Space | O(1) | Only constant extra variables are used |
The feasibility function scans the array once, requiring linear time. Binary search performs a fixed number of iterations determined by floating-point precision. Since the numeric range is bounded and precision is fixed at 10^-5, the number of iterations is effectively logarithmic.
Test Cases
from math import isclose
solution = Solution()
assert isclose(
solution.findMaxAverage(
[1, 12, -5, -6, 50, 3],
4
),
12.75,
abs_tol=1e-5
) # Example 1
assert isclose(
solution.findMaxAverage(
[5],
1
),
5.0,
abs_tol=1e-5
) # Single element case
assert isclose(
solution.findMaxAverage(
[-1, -2, -3],
1
),
-1.0,
abs_tol=1e-5
) # All negative values
assert isclose(
solution.findMaxAverage(
[7, 7, 7, 7],
2
),
7.0,
abs_tol=1e-5
) # Identical values
assert isclose(
solution.findMaxAverage(
[1, 2, 3, 4, 5],
5
),
3.0,
abs_tol=1e-5
) # Entire array required
assert isclose(
solution.findMaxAverage(
[10, -10, 10, -10, 10],
2
),
3.333333,
abs_tol=1e-4
) # Mixed positive and negative values
assert isclose(
solution.findMaxAverage(
[0, 0, 0, 0],
2
),
0.0,
abs_tol=1e-5
) # All zeroes
| Test | Why |
|---|---|
[1,12,-5,-6,50,3], k=4 |
Verifies official example |
[5], k=1 |
Smallest valid input |
[-1,-2,-3], k=1 |
Handles all negative numbers |
[7,7,7,7], k=2 |
Uniform values |
[1,2,3,4,5], k=5 |
Entire array must be selected |
[10,-10,10,-10,10], k=2 |
Mixed signs and varying valid lengths |
[0,0,0,0], k=2 |
Ensures zero averages work correctly |
Edge Cases
Single Element Array
When nums contains only one element and k = 1, the answer must simply be that element itself. Some implementations may fail due to assumptions about longer windows or prefix calculations. This implementation handles the case naturally because the binary search boundaries collapse immediately.
All Negative Numbers
A common mistake is assuming larger sums always improve the average. With negative values, the least negative number may produce the best result. Since the algorithm binary searches over the numeric range and checks transformed sums mathematically, it works correctly regardless of sign.
Best Subarray Longer Than k
A naive sliding window solution may only check windows of size exactly k. However, the problem allows lengths greater than k. The prefix minimum technique ensures every valid subarray of size at least k is considered, not just fixed-length windows.
Identical Values
If all values are equal, the maximum average equals that repeated value. Binary search still converges correctly because every subarray yields the same average, and the feasibility test remains valid throughout the search range.