⚡Flashcard Drill➔
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

  1. Binary search on the average. The predicate "there exists a subarray of length at least k with average at least m" is monotone in m.
  2. To test a candidate m, subtract m from every element and ask whether some subarray of length at least k has a non-negative sum.
  3. That test is done with prefix sums and a running minimum of the prefix values, in O(n).
  4. 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_prefix initial 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 is min(nums).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems