Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/644.html

644. Maximum Average Subarray II

Level

Hard

Description

Given an array consisting of n integers, find the contiguous subarray whose length is greater than or equal to k that has the maximum average value. And you need to output the maximum average value.

Example 1:

Input: [1,12,-5,-6,50,3], k = 4

Output: 12.75

Explanation:

When length is 5, maximum average value is 10.8,

When length is 6, maximum average value is 9.16667.

Thus return 12.75.

Note:

  1. 1 <= k <= n <= 10,000.
  2. Elements of the given array will be in range [-10,000, 10,000].
  3. The answer with the calculation error less than 10-5 will be accepted.

Solution

Use binary search. Initialize min and max to be the minimum element in nums and the maximum element in nums, respectively. Each time calculate mid as the average of min and max, and maintain prevMid which stores the previous value of mid. After mid is calculated, check whether there exists a subarray of nums such that its average value is at least mid. If so, set min = mid. Otherwise, set max = mid. Then calculate the error as the absolute difference between mid and prevMid and set prevMid = mid. The binary search ends when the error does not exceed 10^-5. Finally, return min.

  • class Solution {
    public double findMaxAverage(int[] nums, int k) {
        final double EPSILON = 0.00001;
        double min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        double prevMid = max;
        double error = Integer.MAX_VALUE;
        while (error > EPSILON) {
            double mid = (min + max) / 2;
            if (exist(nums, mid, k))
                min = mid;
            else
                max = mid;
            error = Math.abs(mid - prevMid);
            prevMid = mid;
        }
        return min;
    }

    public boolean exist(int[] nums, double mid, int k) {
        double sum = 0, prefixSum = 0, minSum = 0;
        for (int i = 0; i < k; i++)
            sum += nums[i] - mid;
        if (sum >= 0)
            return true;
        int length = nums.length;
        for (int i = k; i < length; i++) {
            sum += nums[i] - mid;
            prefixSum += nums[i - k] - mid;
            minSum = Math.min(minSum, prefixSum);
            if (sum >= minSum)
                return true;
        }
        return false;
    }
}

  • class Solution(object):
  # just guess the answer by binary search
  # note that we can check if there is a subarray that has avg. sum >= a certain value in linear time
  # then overall time complexity is O(nlog(max(nums) - min(nums)))
  def _findMaxAverage(self, nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: float
    """

    def valid(nums, mid, k):
      minSum = preSums = sums = 0
      for i in range(k):
        sums += nums[i] - mid
      if sums >= 0:
        return True
      for i in range(k, len(nums)):
        sums += nums[i] - mid
        preSums += nums[i - k] - mid
        minSum = min(minSum, preSums)
        if sums - minSum >= 0:
          return True
      return False

    lo = min(nums)
    hi = max(nums)
    while hi - lo > 1e-5:
      mid = (hi + lo) / 2.
      if valid(nums, mid, k):
        lo = mid
      else:
        hi = mid
    return lo

  # have to use this hack to pass OJ
  def findMaxAverage(self, nums, k):
    import numpy as np
    lo, hi = min(nums), max(nums)
    nums = np.array([0] + nums)
    while hi - lo > 1e-5:
      mid = nums[0] = (lo + hi) / 2.
      sums = (nums - mid).cumsum()
      mins = np.minimum.accumulate(sums)
      if (sums[k:] - mins[:-k]).max() > 0:
        lo = mid
      else:
        hi = mid
    return lo

All Problems

All Solutions