Java solution O(nlogM) Binary search the answer


  • 21
    K

    (nums[i]+nums[i+1]+...+nums[j])/(j-i+1)>x
    =>nums[i]+nums[i+1]+...+nums[j]>x*(j-i+1)
    =>(nums[i]-x)+(nums[i+1]-x)+...+(nums[j]-x)>0

    public class Solution {
        boolean check(int[] nums,int k,double x) //Check whether we can find a subarray whose average is bigger than x
        {
            int n=nums.length;
            double[] a=new double[n];
            for (int i=0;i<n;i++) a[i]=nums[i]-x; //Transfer to a[i], find whether there is a subarray whose sum is bigger than 0
            double now=0,last=0;
            for (int i=0;i<k;i++) now+=a[i];
            if (now>=0) return true;
            for (int i=k;i<n;i++)
            {
                now+=a[i];
                last+=a[i-k];
                if (last<0) 
                {
                    now-=last;
                    last=0;
                }
                if (now>=0) return true;
            }
            return false;
        }
        public double findMaxAverage(int[] nums, int k) {
            double l=Integer.MIN_VALUE,r=Integer.MAX_VALUE;
            while (r-l>0.000004) //Binary search the answer
            {
                double mid=(l+r)/2;
                if (check(nums,k,mid)) l=mid; else r=mid;
            }
            return r;
        }
    }
    

  • 0
    Z

    Could you please explain a little bit about

                now+=a[i];
                last+=a[i-k];
                if (last<0) 
                {
                    now-=last;
                    last=0;
                }
    

    this part?


  • 1
    T

    share another version of java solution, similar to your method!

    public class Solution {
        public double findMaxAverage(int[] nums, int k) {
            double low=-100000;
            double high=100000;
            
            int rep=0;
            while(low<high&&rep<100){
                double mid=(low+high)/2;
                if(check(nums,k,mid)){
                    low=mid;
                }else{
                    high=mid;
                }
                
                rep++;
            }
            
            return low;
        }
        
        public boolean check(int[] nums,int k,double target){
            double[] values = new double[nums.length];
            for(int i=0;i<nums.length;i++){
                values[i]=(double)nums[i]-target;
            }
            
            double sum=0;
            double pre_min=0;
            double pre_sum=0;
            
            for(int i=0;i<values.length;i++){
                  sum+=values[i];
                  if(i>=k-1){
                      if(sum-pre_min>=0){
                          return true;
                      }
                      pre_sum+=values[i-(k-1)];
                      pre_min=Math.min(pre_sum,pre_min);
                  }
            }
            
            return false;
        }
    }
    
    

  • 0
    L

    @Zeratul92 Let now = nums[i] + nums[i+1] + ... + nums[j], now.length = (j-i + 1) >= k, then last = nums[i] + nums[i+1] + ... + nums[h], (j - h) >= k. So last is the sum of the first h integers. If last is < 0, then we get rid of all the first h integers, so now will be bigger, because their sum is < 0.

    Hope this helps.


  • 4

    Similar solution with explanation.

    public class Solution {
        public double findMaxAverage(int[] nums, int k) {
            if (nums == null || nums.length <k || k<=0) return Integer.MIN_VALUE;
            double min = nums[0], max = nums[0];
            for(int i=0; i<nums.length; i++){
                if (nums[i]<min) min = nums[i];
                if (nums[i]>max) max = nums[i];
            }
            while (min <= max) { //binary search to find the max average between min and max
                double mid = min +(max-min)/2.0;
                if (hasAvgAbove(nums, k, mid)) {
                    min = mid + 0.000_005; //error less than 10-5 will be accepted.
                } else max = mid - 0.000_005;
            }
            return max;
        }
        
        private boolean hasAvgAbove(int[] nums, int k, double target) {
            double sum = 0, extraSum =0;
            for(int i=0; i<k; i++){
                sum += nums[i]-target;
            }
            // must have at least k elements; the nums before the last k element should be kept if their sum > 0;
            // else we should remove them from the current sum (equivalent to update the start position)
            int curr = k;
            while (curr < nums.length) {
                if (sum >= 0) return true;
                sum += nums[curr] - target;
                extraSum += nums[curr-k] - target;
                if (extraSum < 0) { //update the start position of the current sum
                    sum -= extraSum;
                    extraSum = 0;
                }
                curr ++;
            }
            return sum >= 0;
        }
    }
    

  • 1
    B

    C++ version of the algorithm (about 120ms):

    class Solution {
    private:
        bool larger(vector<int>& nums, int k, double avg) {
            int n=nums.size();
            
            // a number will increase the average if it is larger than average
            // hence we prepare a differences vector to see if a number
            // can be added to increse the average
            vector<double> diffs(n);
            for (int i=0; i<n; i++) diffs[i]=nums[i]-avg;
            double maxsum=accumulate(diffs.begin(),diffs.begin()+k,0.0);
            
            if (maxsum>=0) return true;
            
            double leftsum=0;
            
            // keeping incrementing the right side of the window
            for (int i=k; i<n; i++) {
                maxsum+=diffs[i];
                leftsum+=diffs[i-k];
                
                // reset the left side of the window to zero, if below zero
                // note: maxsum has at least k elements,
                // maxsum has exactly k elements after a reset
                if (leftsum<0) {
                    maxsum-=leftsum;
                    leftsum=0;
                }
                
                if (maxsum>=0) return true;
            }
            return false;
        }
    public:
        double findMaxAverage(vector<int>& nums, int k) {
            double l=*min_element(nums.begin(),nums.end());
            double r=*max_element(nums.begin(),nums.end());
            double m;
            
            while (r-l>0.000009) {
                m=(l+r)/2;
                if (larger(nums,k,m)) l=m;
                else r=m;
            }
            
            return l;
        }
    };
    

  • 0
    N

    @LeetCoding very good explanation.

    A little improvement

                    if (sum >= 0) return true; // for any k+ elements once sum>=0 , we find the result and can return true.
                    cur++;
    

  • 1
    K

    @Zeratul92
    "now" stores the sum of our subarray (make sure it has at least k numbers)
    "last" stores the sum of the extra part of subarray (for example, if k=4, and our subarray is from 7 to 13, then 7-9 is the extra part.) if last<0, we can easily remove the extra part, to get a larger sum.


  • 0

    Cool. The C++ binary search solution could be found here: https://discuss.leetcode.com/topic/96228/clean-c-binary-search-solution-with-explanation


  • 0

    it seems like that there still is a trick for the r-l>0.000004, why do not use some other num like 0.000001? Besides,in your case when the now variable in check function equals to 0, the function returns true and the mid would be assigned to l, which means l is the real average,but why do you return r rather than l? Thanks


  • 0
    X
    This post is deleted!

  • 2

    Alternate Solution which has only O(1) Space Complexity:

    public double findMaxAverage(int[] nums, int k) {
        double l = -10000, r = 10000;
        while (r - l > 10e-7) {
            double mid = (l+r)/2; 
            if (getMaxSubbaraySumOfSizeK(nums, k, mid) >= 0) l = mid;
            else r = mid;
        }
        return (l+r)/2;
    }
    
    public double getMaxSubbaraySumOfSizeK(int[] nums, int k, double mid) {
        double sum = 0.0;
        for (int i=0;i<=k-1;i++) sum += nums[i] - mid;
        double maxSum = sum, prev = nums[0] - mid;
        for (int i=k;i<nums.length;i++) {
             sum = sum - nums[i-k] + nums[i];
             maxSum = Math.max(maxSum, Math.max(sum, sum + prev));
             prev = Math.max(nums[i-k+1], nums[i-k+1] + prev) - mid;
        }
        return maxSum;
    }
    

  • 0

    Here is my solution

    public class Solution {
        public double findMaxAverage(int[] nums, int k) {
            double low = -10001, high = 10001;
            for(int rep = 0;rep < 100;rep++){
                double h = (low+high)/2;
                if(fun(h, nums, k)){
                    low = h;
                }else{
                    high = h;
                }
            }
            return low;
        }
    
        private boolean fun(double h, int[] nums, int k){
            int n = nums.length;
            double[] cum = new double[n+1];
            for(int i = 0;i < n;i++){
                cum[i+1] = cum[i] + nums[i] - h;
            }
            double min = Double.POSITIVE_INFINITY;
            for(int i = k-1;i < n;i++){
                min = Math.min(min, cum[i-(k-1)]);
                if(cum[i+1] - min >= 0)return true;
            }
            return false;
        }
    }
    

  • 0
    J

    python version. took me a while to understand the validation part.

    max(presum[j] - presum[i] - (sub array length)*mean)  
    = max(nums[i+1]-mean + nums[i+2]-mean + ... + nums[j]-mean)
    = presum[j]-(sub array length)*mean - min(presum[i] - (sub array length)*mean)
    
    

    min_pre_sum is initialized to 0, which means sum is from 0 to j. This is the base case.

    class Solution(object):
        def findMaxAverage(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: float
            """
            if nums is None or len(nums)<k: return 0.0
            l, h = min(nums), max(nums)
            while l < h - 0.00001:
                mid = l + (h-l)/2.0
                if self.larger_than(nums, k, mid):
                    l = mid
                else:
                    h = mid
            return l
        
        def larger_than(self, nums, k, mean):
            sum_so_far = 0
            for i in xrange(k):
                sum_so_far += nums[i] - mean
            if sum_so_far>=0:
                return True
            min_pre_sum = 0
            pre_sum = 0
            for i in xrange(k, len(nums)):
                sum_so_far += nums[i] - mean
                pre_sum += nums[i-k] -  mean
                min_pre_sum = min(min_pre_sum, pre_sum)
                if sum_so_far >= min_pre_sum:
                    return True
            return False
    

  • 0
    D

    I don't know how to use this rule:

    The answer with the calculation error less than 10-5 will be accepted.
    

    why we use 0.000_004 instead of like 0.000_009 or 0.000_001 or other numbers less than 0.000_01?


  • 0
    P

    For the time complexity, I understand O(n) is from each "check()" on the entire nums array. Does M == (Integer.MAX_VALUE - Integer.MIN_VALUE) ? so it will be O(n log ( Integer.MAX_VALUE - Integer.MIN_VALUE)).

    I think people mentioned in the earlier post that since the array element domain is between -10000 and 10000. We can tighten the time complexity to O(n log ( 20000) ), which can be approximated to O(n)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.