NeetCode #271LC-644HardBinary SearchNC Algo100
← Back to All Problems#271 · #644 · Maximum Average Subarray II(最大平均子段和 II)
📌 Problem Statement & Constraints
You are given an array
nums of integers and an integer k. Find a contiguous subarray of length at least k with the maximum average value, and return that average. Constraints: 1 <= k <= nums.length <= 10^4, -10^4 <= nums[i] <= 10^4. The answer with a calculation error of 10^-5 is accepted.💡 Core Algorithmic Approaches
- Binary search on the average. The predicate "there exists a subarray of length at least
kwith average at leastm" is monotone inm. - To test a candidate
m, subtractmfrom every element and ask whether some subarray of length at leastkhas a non-negative sum. - That test is done with prefix sums and a running minimum of the prefix values, in O(n).
- Because the answer is a real number, iterate the binary search a fixed number of times (about 60) instead of looping on
lo < hi.
💻 Benchmark Python3 Implementation
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
lo, hi = min(nums), max(nums)
for _ in range(60): # enough iterations for 1e-5 precision
mid = (lo + hi) / 2
# prefix sums of (nums[i] - mid)
prefix = [0.0] * (len(nums) + 1)
for i, x in enumerate(nums):
prefix[i + 1] = prefix[i] + x - mid
# exists a window of length >= k with sum >= 0?
ok = False
min_prefix = 0.0
for i in range(k, len(prefix)):
min_prefix = min(min_prefix, prefix[i - k])
if prefix[i] - min_prefix >= 0:
ok = True
break
if ok:
lo = mid # mid is achievable -> try higher
else:
hi = mid
return lo⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n * iterations) = O(60n): each feasibility test is a linear scan.
💾 Space Complexity
O(n) for the prefix array (O(1) with a rolling computation of the minimum).
⚠️ Interview Pitfalls & Follow-ups
- Binary searching on integers: the answer is a real number, so a fixed iteration count is needed.
- Using
while lo < hi: floating-point comparisons can stall; a fixed iteration count is robust. - Checking only windows of length exactly
k: the window may be longer, which is why the prefix-minimum technique is used. - Forgetting the
min_prefixinitial value of 0: it represents the empty prefix, which allows windows starting at index 0. - Setting the search bounds to
[0, max(nums)]: negative values are allowed, so the lower bound ismin(nums).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.