Maximum Average Subarray II

How it works

Instead of checking all subarrays, we can binary search on the answer. The key insight is that the maximum average lies between the minimum and maximum values in the array. For a candidate average mid, we can efficiently check if there exists a subarray of length at least k with average greater than or equal to mid.

To check this, we subtract mid from each element. Now we need to find a subarray of length at least k with non-negative sum. Using prefix sums and tracking the minimum prefix sum before the current window, we can do this in linear time.

Steps

1. Initialize min_val and max_val as the minimum and maximum of nums.
2. Binary search while the error exceeds 0.00001:
   • Compute mid = (min_val + max_val) / 2.
   • Call check(nums, mid, k) to see if a valid subarray exists.
   • If true, set min_val = mid (answer is at least mid).
   • Otherwise, set max_val = mid.
3. The check function:
   • Compute prefix sums of nums[i] - mid.
   • Track min_sum as the minimum prefix sum seen at least k positions before.
   • If current_sum - min_sum >= 0 at any point, return true.
4. Return min_val.

Complexity

• Time complexity: O(N × log_2 frac{(text{max_val} - text{min_val})}{0.00001}).
  • The algorithm consists of a binary search loop in the function of findMaxAverage().
  • At each iteration of the loop, the check() function dominates the time complexity, which is of O(N) for each invocation.
  • It now boils down to how many iterations the loop would run eventually. To calculate the number of iterations, let us break it down in the following steps.
  • After the first iteration, the error would be frac{text{range}}{2}, as one can see. Further on, at each iteration, the error would be reduced into half. For example, after the second iteration, we would have the error as frac{text{range}}{2} × frac{1}{2}.
  • As a result, after K iterations, the error would become text{error} = text{range} × 2^{-K}. Given the condition of the loop, i.e. text{error} < 0.00001, we can deduct that K > log_2 frac{text{range}}{0.00001} = log_2 frac{(text{max_val} - text{min_val})}{0.00001}.
  • To sum up, the time complexity of the algorithm would be O(N × K) = O(N × log_2 frac{(text{max_val} - text{min_val})}{0.00001}).
• Space complexity: O(1) constant space

Where N is the number of elements in the array, and range is the difference between the maximal and minimal values in the array, i.e. range = max_val - min_val, and finally error is the precision required in the problem.

Things to watch for

Forgetting the Minimum Length Constraint

The subarray must have length at least k. A common mistake is to check all subarrays without enforcing this constraint, or to only check subarrays of exactly length k and miss longer subarrays that could have a higher average.

Floating-Point Precision Issues

Binary search on real numbers requires careful handling of precision. Setting the tolerance too tight can cause infinite loops, while setting it too loose yields inaccurate answers. The epsilon value of 0.00001 must be chosen to match the problem's precision requirements.

Incorrect Check Function Logic

The check function determines if a subarray with average at least mid exists. The trick of subtracting mid from each element and finding a non-negative sum subarray is subtle. Errors in tracking prefix sums or the minimum prefix sum lead to false positives or negatives.

Not Tracking Minimum Prefix Sum Correctly

In the check function, you need the minimum prefix sum that ends at least k positions before the current index. Off-by-one errors in when to update min_sum versus when to use it cause the check to return incorrect results.

Binary Search Direction Confusion

When the check returns true, it means a valid subarray exists with average at least mid, so the answer is at least mid and we should search higher. Reversing this logic inverts the binary search and produces wrong answers.

from typing import List

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        max_val = float('-inf')
        min_val = float('inf')
        for n in nums:
            max_val = max(max_val, n)
            min_val = min(min_val, n)

        prev_mid = max_val
        error = float('inf')

        while error > 0.00001:
            mid = (max_val + min_val) * 0.5
            if self.check(nums, mid, k):
                min_val = mid
            else:
                max_val = mid
            error = abs(prev_mid - mid)
            prev_mid = mid

        return min_val

    def check(self, nums: List[int], mid: float, k: int) -> bool:
        sum_val = 0
        prev = 0
        min_sum = 0

        for i in range(k):
            sum_val += nums[i] - mid

        if sum_val >= 0:
            return True

        for i in range(k, len(nums)):
            sum_val += nums[i] - mid
            prev += nums[i - k] - mid
            min_sum = min(prev, min_sum)
            if sum_val >= min_sum:
                return True

        return False

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double max_val = INT_MIN;
        double min_val = INT_MAX;

        for (int n : nums) {
            max_val = max(max_val, (double)n);
            min_val = min(min_val, (double)n);
        }

        double prev_mid = max_val;
        double error = INT_MAX;

        while (error > 0.00001) {
            double mid = (max_val + min_val) * 0.5;
            if (check(nums, mid, k))
                min_val = mid;
            else
                max_val = mid;
            error = abs(prev_mid - mid);
            prev_mid = mid;
        }

        return min_val;
    }

private:
    bool check(vector<int>& nums, double mid, int k) {
        double sum = 0, prev = 0, min_sum = 0;

        for (int i = 0; i < k; i++)
            sum += nums[i] - mid;

        if (sum >= 0)
            return true;

        for (int i = k; i < nums.size(); i++) {
            sum += nums[i] - mid;
            prev += nums[i - k] - mid;
            min_sum = min(prev, min_sum);
            if (sum >= min_sum)
                return true;
        }

        return false;
    }
};