LeetCode Solutions Blog

Maximum Average Subarray I

Number: 643

Difficulty: Easy

Paid? No

Problem Description

Given an integer array and an integer k, find a contiguous subarray of length k that has the maximum average value.

Key Insights

Use a sliding window to efficiently compute the sum of every subarray of length k.
Maintain the maximum sum encountered while sliding the window across the array.
Finally, calculate the average of the subarray with the maximum sum by dividing by k.

Space and Time Complexity

Time Complexity: O(n) - We compute the initial sum in O(k) and then update the sum in O(n-k). Space Complexity: O(1) - Only a few extra variables are used regardless of input size.

Solution

Use the sliding window technique. Start by computing the sum of the first k elements. As you slide the window forward one index at a time, subtract the element that is leaving the window and add the new element that enters the window. Maintain a variable to track the maximum sum seen so far. Finally, the maximum average is the maximum sum divided by k.

Code Solutions

# Python solution using the sliding window technique

def findMaxAverage(nums, k):
    # Calculate the initial sum of the first window of size k
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    # Slide the window from index k to the end of the array
    for i in range(k, len(nums)):
        # Update the sum by subtracting the element that is sliding out
        # and adding the new element
        window_sum += nums[i] - nums[i - k]
        # Update max_sum if the new window_sum is higher
        max_sum = max(max_sum, window_sum)
    
    # Return the maximum average found
    return max_sum / k

# Example usage:
# nums = [1, 12, -5, -6, 50, 3]
# k = 4
# print(findMaxAverage(nums, k))  # Output: 12.75