Maximum Average Subarray II Python Solution

lcpy gen -n 644   # by problem number
lcpy gen -s maximum_average_subarray_ii   # by problem name

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: When the length is 4, averages are [0.5, 12.75, 10.5] and the maximum average is 12.75. We do not consider subarrays of length < 4.

Input: nums = [5], k = 1
Output: 5.00000

class Solution:
    # Time: O(n log M) where M = max(nums) - min(nums)
    # Space: O(1)
    def find_max_average(self, nums: list[int], k: int) -> float:
        def check(v: float) -> bool:
            s = sum(nums[:k]) - k * v
            if s >= 0:
                return True
            t = mi = 0.0
            for i in range(k, len(nums)):
                s += nums[i] - v
                t += nums[i - k] - v
                mi = min(mi, t)
                if s >= mi:
                    return True
            return False

        eps = 1e-5
        lo, hi = min(nums), max(nums)
        while hi - lo >= eps:
            mid = (lo + hi) / 2
            if check(mid):
                lo = mid
            else:
                hi = mid
        return lo