644. Maximum Average Subarray II

This problem asks to find the maximum average value of a contiguous subarray with length greater than or equal to k. The solution employs binary search for efficiency.

Approach: Binary Search with Prefix Sum Optimization

The core idea is to use binary search to find the maximum average. The search space is bounded by the minimum and maximum values in the input array nums. For each potential average v considered during the binary search, we need to efficiently check if there exists a subarray with length >= k whose average is >= v.

Checking for a Subarray with Average >= v:

Instead of directly checking averages, we transform the problem. If a subarray's average is >= v, then the sum of its elements minus v * (subarray length) must be >= 0. This allows us to work with sums instead of averages.

We iterate through the array, maintaining a running sum of (nums[i] - v). The condition (nums[i] - v) + ... + (nums[j] - v) >= 0 is equivalent to checking if a subarray from i to j has an average >= v.

To efficiently handle the length constraint (>= k), we use a sliding window technique and track the minimum prefix sum within the window. If the current running sum is greater than or equal to this minimum prefix sum, it indicates the existence of a subarray satisfying the conditions.

Binary Search:

The binary search iteratively narrows down the search space. If a v satisfies the condition (a subarray with average >= v exists), we move the lower bound of the search to v. Otherwise, we move the upper bound. The search continues until the difference between the upper and lower bounds is smaller than a predefined tolerance (eps). The final lower bound is the maximum average.

Time and Space Complexity

• Time Complexity: O(n log M), where n is the length of nums and M is the range of values in nums (max - min). The log M factor comes from the binary search, and the n factor arises from the linear scan of the array within the check function.
• Space Complexity: O(1). The algorithm uses only a constant amount of extra space.

Code Implementation (Python)

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        def check(v: float) -> bool:
            s = sum(nums[:k]) - k * v  # Initial sum of (nums[i] - v) for the first k elements
            if s >= 0:
                return True  # Found a subarray of length k with average >= v
            t = mi = 0  # Initialize variables for sliding window
            for i in range(k, len(nums)):
                s += nums[i] - v  # Update running sum
                t += nums[i - k] - v # Update the sum to be removed from the window
                mi = min(mi, t)  # Keep track of the minimum prefix sum in the window
                if s >= mi:  # Check if there's a subarray with average >= v
                    return True
            return False  # No such subarray found
 
        eps = 1e-5
        l, r = min(nums), max(nums)  # Initialize search space
        while r - l >= eps:
            mid = (l + r) / 2
            if check(mid):
                l = mid  # Move lower bound if condition is met
            else:
                r = mid  # Move upper bound otherwise
        return l  # Final lower bound is the maximum average
 

Implementations in other languages (Java, C++, Go, TypeScript) follow a similar structure, adapting the syntax and standard libraries as needed. The core logic of binary search and the sliding window technique remain the same.