This is a binary search solution, should be O(nlog(m)). Still getting time out?
def findMaxAverage(self, nums, k): hi, lo = max(nums), min(nums) arr = [0.0] * (len(nums) + 1) def isTrueAvgHigher(avg): minval = 2**32 for i in xrange(len(nums)): arr[i+1] = nums[i] + arr[i] - avg if i >= (k-1): if arr[i-k+1] < minval: minval = arr[i-k+1] if arr[i+1] - minval >= 0: return True return False while (hi - lo) > 1e-5: mid = 1.0 * (hi + lo) / 2 if isTrueAvgHigher(mid): lo = mid else: hi = mid return 1.0*(hi+lo)/2
#Edit: following is an O(N) solution using similar idea as above, except you directly calculate how much average you need to add to get to the true solution.
def findMaxAverage(self, nums, k): arr = [0.0] * (len(nums) + 1) def getDelta(avg): minval, minval_pos = 2**32, -1 delta = 0 for i in xrange(len(nums)): arr[i+1] = nums[i] + arr[i] - avg if i >= (k-1): if arr[i-k+1] < minval: # keep track of lowest average sum . minval = arr[i-k+1] minval_pos = i-k+1 if arr[i+1] - minval >= 0: # calculate the diff you need to add to reach the true average. delta = max(delta, 1.0 * (arr[i+1] - minval) / (i+1 - minval_pos)) return delta lo = min(nums) # use minimum as initial guess. for i in range(4): # Should only take 1 iteration, but need at least 4 iterations due to machine precision in calculating average for large arrays. lo += getDelta(lo) return lo
The range of your binary search is : max(nums) - min(nums), which can be really large.
@totolipton Great solution!
@BigBiang The constant should be no more than log_2 (20000 * e^5), which is roughly 28 which should be OK?
@flamesofmoon I guess you are right. This shouldn't be the problem.
In O( n * log(m) ) what is "m" here? n understandably is nums length as isTrueAvgHigher runs over all items and m is height of binary search tree, which would be log2(hi - lo)?
Here is my attempt, it times out for nums with 10000 numbers
Not sure about complexity - probably O( n**2 ) but inner loop gets shorter as i increases,
class Solution(object): def findMaxAverage(self, nums, k): """ :type nums: List[int] :type k: int :rtype: float """ n = len(nums) sums = [(0,0)] * (n - k + 1) sums = (sum(nums[:k]), k) for i in range(1, n - k + 1): sums[i] = (sums[i - 1] - nums[i - 1] + nums[i + k - 1], k) for i in range(n - k + 1): oldsum, oldn = sums[i] newsum = oldsum newn = oldn for j in range(i+k, n): newsum += nums[j] newn += 1 if oldsum/float(oldn) < (newsum)/float(newn): oldsum = newsum oldn = newn sums[i] = (newsum,newn) maxsum, maxk = max(sums, key=lambda x: x/float(x)) return maxsum / maxk
here? n understandably is nums length as isTrueAvgHigher runs over all items and m is height of binary search tree, which would be log2(hi
Hi Parvez, yes, here the "m" = (hi - lo). The method you posted is indeed O(N**2).
Thanks for the solution. Really smart.
Regarding O(N) solution, I have hard time understand the correctness of the algorithm. Especially this line
for i in range(4): # Should only take 1 iteration, but need at least 4 iterations due to machine precision in calculating average for large arrays.
If you try [1,5,3], 2
Then the algorithm needs 2 iterations to get the correct solution. So I think there are some math behind it to make sure 4 is enough, otherwise I am wondering there are cases where 4 iteration is not enough.
@yanzhan2 The "O(n)" solution is incorrect. When we chose the smallest minval (and it's corresponding position), there was no guarantee that the average over that interval is the largest, only the guarantee that we are choosing averages better than our initial guess. Essentially, we are using a greedy algorithm to refine our guess.
We can construct a counterexample like
A[i] = i. When N = 10000, K = 1, we need 14 iterations. We can probably construct more elaborate counterexamples. My guess is the solution offered has a counterexample that makes the algorithm
N^2 (or perhaps
N^(3/2), but definitely not
N), but I haven't searched very far.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.