Hard

Maximum Average Subarray II

LAB

Return the maximum average among subarrays with length at least k.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    12,
    -5,
    -6,
    50,
    3
  ],
  "k": 4
}

Output
12.75

FUNCTION SHAPE

nums: intArrayk: int→double

SOLUTION NOTE

Binary search on the average value. Key insight: subtract candidate avg from all elements, then find subarray of len >= k with sum >= 0. Uses prefix sum with delayed minimum tracking.

Reveal reference solution +

pythonREFERENCE

def findMaxAverage(self, nums: List[int], k: int) -> float:
    def check(avg):
        # Transform: can we find subarray of len >= k with sum >= 0?
        # After subtracting avg from each element
        min_prefix = float('inf')
        prefix = 0
        lagging_prefix = 0

        for i in range(len(nums)):
            prefix += nums[i] - avg
            if i >= k - 1:
                if i == k - 1:
                    min_prefix = 0
                if prefix >= min_prefix:
                    return True
                lagging_prefix += nums[i - k + 1] - avg
                min_prefix = min(min_prefix, lagging_prefix)
        return False

    left, right = min(nums), max(nums)
    while right - left >= 1e-5:
        mid = left + (right - left) / 2
        if check(mid):
            left = mid
        else:
            right = mid
    return left

TimeO(n log((max-min)/ε))

SpaceO(1)

Open on LeetCode ↗