Problem statement

https://leetcode.com/problems/maximum-average-subarray-ii/

Solution 1

Let us first understand how to answer to question: is there subarray of length >= k, such that its average is >= T. It means, that if we subtract T from all numbers, then we need to find subarray with length >= k with sum >= 0. It can be done in O(n): evaluate cumulative sums and then we need to keep minimum among first i-k numbers and check if nums[i] more than this minimum. Then we do binary search on these problems, looking for T.

Complexity

Overall time complexity is O(n * log M), where $M$ is sum of all absolute values of array. Also note, that we need to use not integer beg and end to converge to 10^{-5}.

Code

class Solution:
    def findMaxAverage(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)/2
            if checkSum(nums, mid):
                beg = mid
            else:
                end = mid
        return beg

Solution 2

There is also very interesting solution, using convex hulls with $O(n)$ complexity, where I understand only idea, solution is quite difficult. Idea is to interpret our data as finding maximum of (S_i - S_j)/(i-j), so we can interpret (i, S_i) as points on plane. I think it is also similar to idea of monotonic deque.

Complexity

Time complexity is O(n), space as well.

Code

class Solution:
    def findMaxAverage(self, nums, k):
        n = len(nums)
        P = [0] + list(accumulate(nums))
        
        def d(x, y):
            return (P[y+1] - P[x]) / (y+1-x)
            
        hull = deque()
        ans = float("-inf")
        
        for j in range(k-1, n):
            while len(hull) >= 2 and d(hull[-2], hull[-1]-1) >= d(hull[-2], j-k):
                hull.pop()
            hull.append(j-k+1)
            while len(hull) >= 2 and d(hull[0], hull[1]-1) <= d(hull[0], j):
                hull.popleft()
            ans = max(ans, d(hull[0], j))
            
        return ans