Maximum Average Subarray

Sliding Window

Problem

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value

For example:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4
= 51/4 = 12.75

Thought Process

• We can apply Sliding Window Technique since we are asked to find length of contingous subarray

• This is a static window so we are removing an element before we add a new one (this is why >= k-1)

Solution

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        maxAvg = float('-inf')
        totalAvg = 0
        start = 0
        
        for i in range(len(nums)):
            totalAvg+=nums[i]
            
            if i >= k-1:
                newAvg = totalAvg/k
                maxAvg = max(maxAvg, newAvg)
                totalAvg-=nums[start]
                start+=1
                
        return maxAvg
        

Key Points

• We are using a static window of a fixed size and moving in blocks of size k

Time Complexity

• Time $O(n)$

• Space: $O(1)$