LeetCode Solutions Blog

Maximum Average Subarray II

Number: 644

Difficulty: Hard

Paid? Yes

Companies: Google

Problem Description

Given an integer array nums and an integer k, find a contiguous subarray with length at least k that has the maximum average value and return this maximum average. The answer is accepted within a precision error of less than 10⁻⁵.

Key Insights

Use binary search on the possible average values rather than on indices.
Transform the problem by subtracting the candidate average from each element.
Use prefix sum and the minimum prefix sum seen so far to check if a subarray of length at least k has a non-negative sum, indicating that the candidate average is achievable.
Narrow the search range until the required precision is met.

Space and Time Complexity

Time Complexity: O(n * log(max - min) / precision)
Space Complexity: O(n)

Solution

The solution uses binary search to "guess" the maximum average. For each candidate average, subtract it from each element to create a transformed array. Then, determine if there exists a subarray (of length at least k) in the transformed array with a non-negative sum. This is done using prefix sums along with tracking the minimum prefix sum encountered. If such a subarray exists, it means the candidate average is achievable, and you can adjust the binary search accordingly. This approach leverages prefix sum computations, which are O(n) per binary search iteration.

Code Solutions

def findMaxAverage(nums, k):
    # define the helper function to check if candidate average is achievable
    def canFind(sub_avg):
        n = len(nums)
        # transformed array, where each num becomes num - sub_avg
        prefix_sums = [0] * (n + 1)
        for i in range(1, n + 1):
            prefix_sums[i] = prefix_sums[i - 1] + (nums[i - 1] - sub_avg)
        
        # min_prefix up to index i - k ensures subarray length >= k
        min_prefix = 0
        for i in range(k, n + 1):
            # if current prefix sum minus the smallest prefix sum so far is non-negative,
            # then there exists a subarray with average >= sub_avg.
            if prefix_sums[i] - min_prefix >= 0:
                return True
            # update the min_prefix for indices up to i - k + 1
            min_prefix = min(min_prefix, prefix_sums[i - k + 1])
        return False

    # set initial boundaries for binary search
    low, high = min(nums), max(nums)
    precision = 1e-5
    # run binary search until the computed range is under precision
    while high - low > precision:
        mid = (low + high) / 2.0
        if canFind(mid):
            low = mid  # candidate is achievable, search for a higher average
        else:
            high = mid  # candidate not achievable, reduce search space
    return low

# Example usage:
nums = [1,12,-5,-6,50,3]
k = 4
print(findMaxAverage(nums, k))  # Expected output around 12.75000