BinarySearch 0647 Largest Average of Sublist with Length at Least K

Problem statement

https://binarysearch.com/problems/Largest-Average-of-Sublist-with-Length-at-Least-K/

Solution

Equal to Leetcode 0644 Maximum Average Subarray II.

Complexity

It is O(n log M) for time and O(n) for space.

Code

class Solution:
    def solve(self, nums, k):
        n = len(nums)
        
        def checkSum(nums, T):
            nums = [0] + list(accumulate([i-T for i in nums]))
            minim = float("inf")
            for i in range(k, n+1):
                minim = min(minim, nums[i-k])
                if nums[i] >= minim: return True
            return False

        beg, end = -10000, 10000

        while end - beg > 1e-5:
            mid = (beg + end)/2q
            if checkSum(nums, mid):
                beg = mid
            else:
                end = mid
        return beg