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;
        }
    }
    
  • Todo
    
  • 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