Python time limit too tight? O(nlog(m)) solution time out. O(n) solution passes.


  • 3
    T

    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
    

  • 0

    The range of your binary search is : max(nums) - min(nums), which can be really large.


  • 1

    @totolipton Great solution!

    @BigBiang The constant should be no more than log_2 (20000 * e^5), which is roughly 28 which should be OK?


  • 0

    @flamesofmoon I guess you are right. This shouldn't be the problem.


  • 0
    S

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


  • 0
    S

    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[0] = (sum(nums[:k]), k)  
            for i in range(1, n - k + 1):
                sums[i] = (sums[i - 1][0] - 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[0]/float(x[1]))
            return maxsum / maxk

  • 0
    This post is deleted!

  • 0
    T

    @parvez.h.shaikh said in Python time limit too tight?:

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


  • 0
    Y

    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.


  • 1

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


  • 0
    Y

    @awice Thanks for the explanation, make sense.


  • 0
    T

    @awice good catch. I only tried 4 using trial and error to pass all the cases. I am also not sure about the reason behind it.


Log in to reply
 

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