# Java solution O(nlogM) Binary search the answer

• (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;
}
}
``````

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

this part?

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

``````

• @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.

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

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

• @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++;
``````

• @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.

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

• 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

• This post is deleted!

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

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

• 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
``````

• 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?

• 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)

• I prefer this one better than that Math one. I think this is what the interviewer is looking for. As for the error control, I think as long as it's a number <= 10-5 Is okay, and under that condition, whether return r or l is fine.

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