Problem Description

The Maximum Average Subarray II problem requires you to find the contiguous subarray of length at least k within a given array nums (of length n) that has the maximum average value. You must return this maximum average as a floating-point number, with an acceptable error of up to 10-5.

• Input: An integer array nums and an integer k (where 1 <= k <= n <= 104).
• Output: The maximum average of any contiguous subarray of length at least k.
• Each element in nums is within the range [-104, 104].
• There is a guarantee that at least one valid subarray exists.

Thought Process

The first idea is to use a brute-force approach: try every possible subarray of length at least k, calculate its average, and keep track of the maximum. However, with n up to 104, this would require checking O(n²) subarrays, which is too slow.

We need a more efficient way. Notice that since the array can have both positive and negative numbers, and the subarray must be contiguous, we can't simply sum the largest k numbers. Instead, we can ask: "Given an average value x, is there a subarray of length at least k with an average at least x?" If we can efficiently check this for any x, we can use binary search to find the maximum possible average.

This leads to a shift from searching for the subarray itself to searching for the answer (the average) using binary search, and checking feasibility at each step.

Solution Approach

• Binary Search on the Average:
  • Set the initial search range to the minimum and maximum values in nums.
  • While the search interval is larger than 1e-5, perform the following:
    • Guess a mid-value mid between left and right.
    • Check if there is a subarray of length at least k with an average at least mid.
    • If yes, move the left bound up to mid (try for a higher average); else, move the right bound down to mid.
• Checking Feasibility (Prefix Sums):
  • Transform the problem: For a guess x, subtract x from every element in nums, and check if there is a subarray of length at least k whose sum is at least 0.
  • Use prefix sums to efficiently check for such a subarray:
    • Compute the prefix sums of the transformed array.
    • For each index i (starting from k), check if prefix[i] - min(prefix[0..i-k]) >= 0.
• Why This Works:
  • Binary search is justified because the function "is there a subarray with average at least x?" is monotonic: if it's true for x, it's true for any smaller x.
  • Using prefix sums makes checking each guess efficient, reducing the overall time complexity.

Example Walkthrough

Let's consider nums = [1,12,-5,-6,50,3] and k = 4.

1. Set left = -6 (min value), right = 50 (max value).
2. Guess mid = (left + right) / 2 = 22. Subtract 22 from each element and compute prefix sums:
   • Transformed: [-21, -10, -27, -28, 28, -19]
   • Prefix sums: [0, -21, -31, -58, -86, -58, -77]
   No subarray of length 4 has sum >= 0, so set right = 22.
3. Repeat with new mid, narrowing the interval.
4. Eventually, the answer converges to around 12.75, which is the average of subarray [12, -5, -6, 50].

At each binary search step, we efficiently check for a feasible subarray by maintaining the minimum prefix sum for the window.

Code Implementation

class Solution:
    def findMaxAverage(self, nums, k):
        def can_find(avg):
            prefix = [0]
            for num in nums:
                prefix.append(prefix[-1] + num - avg)
            min_prefix = 0
            for i in range(k, len(prefix)):
                if prefix[i] - min_prefix >= 0:
                    return True
                min_prefix = min(min_prefix, prefix[i - k + 1])
            return False
        
        left, right = min(nums), max(nums)
        eps = 1e-5
        while right - left > eps:
            mid = (left + right) / 2
            if can_find(mid):
                left = mid
            else:
                right = mid
        return left
      

class Solution {
public:
    bool canFind(vector<int>& nums, int k, double avg) {
        int n = nums.size();
        vector<double> prefix(n+1, 0);
        for (int i = 0; i < n; ++i)
            prefix[i+1] = prefix[i] + nums[i] - avg;
        double min_prefix = 0;
        for (int i = k; i <= n; ++i) {
            if (prefix[i] - min_prefix >= 0)
                return true;
            min_prefix = min(min_prefix, prefix[i - k + 1]);
        }
        return false;
    }

    double findMaxAverage(vector<int>& nums, int k) {
        double left = *min_element(nums.begin(), nums.end());
        double right = *max_element(nums.begin(), nums.end());
        double eps = 1e-5;
        while (right - left > eps) {
            double mid = (left + right) / 2;
            if (canFind(nums, k, mid))
                left = mid;
            else
                right = mid;
        }
        return left;
    }
};
      

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double left = Integer.MAX_VALUE, right = Integer.MIN_VALUE;
        for (int num : nums) {
            left = Math.min(left, num);
            right = Math.max(right, num);
        }
        double eps = 1e-5;
        while (right - left > eps) {
            double mid = (left + right) / 2;
            if (canFind(nums, k, mid)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }
    private boolean canFind(int[] nums, int k, double avg) {
        int n = nums.length;
        double[] prefix = new double[n + 1];
        for (int i = 0; i < n; ++i)
            prefix[i + 1] = prefix[i] + nums[i] - avg;
        double min_prefix = 0;
        for (int i = k; i <= n; ++i) {
            if (prefix[i] - min_prefix >= 0)
                return true;
            min_prefix = Math.min(min_prefix, prefix[i - k + 1]);
        }
        return false;
    }
}
      

var findMaxAverage = function(nums, k) {
    function canFind(avg) {
        let prefix = [0];
        for (let num of nums)
            prefix.push(prefix[prefix.length - 1] + num - avg);
        let min_prefix = 0;
        for (let i = k; i < prefix.length; ++i) {
            if (prefix[i] - min_prefix >= 0)
                return true;
            min_prefix = Math.min(min_prefix, prefix[i - k + 1]);
        }
        return false;
    }
    let left = Math.min(...nums), right = Math.max(...nums);
    let eps = 1e-5;
    while (right - left > eps) {
        let mid = (left + right) / 2;
        if (canFind(mid))
            left = mid;
        else
            right = mid;
    }
    return left;
};
      

Time and Space Complexity

• Brute-force Approach:
  • Time: O(n²) — For each subarray of length at least k, compute the sum and average.
  • Space: O(1) — Only a few variables for tracking max average.
• Optimized (Binary Search + Prefix Sum):
  • Time: O(n log(R/ε)), where R is the range of values in nums and ε is the precision (1e-5). Each binary search step takes O(n).
  • Space: O(n) — For the prefix sum array.

The optimized approach is efficient enough for the problem's constraints.

Summary

The key insight for Maximum Average Subarray II is to use binary search on the answer (average) and check feasibility using prefix sums. This reduces the problem from O(n²) to O(n log(R/ε)), making it practical for large arrays. The approach elegantly leverages the monotonicity of the feasibility function and efficient prefix sum calculations, making it a classic example of applying binary search in non-obvious ways.