Short and fast Python


  • 3

    Just implementing the binary search solution using NumPy for brevity and efficiency. Gets accepted in about 260 ms, easily beating 100% in the current runtime distribution (where times range from 439 ms to 1892 ms).

    import numpy as np
    
    class Solution(object):
        def findMaxAverage(self, nums, k):
            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
    

  • 0
    Y
    This post is deleted!

Log in to reply
 

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