We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Average Subarray I

Difficulty: Easy

Problem Description

You are given an integer array nums consisting of n elements, and an integer k. Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10^-5 will be accepted.

Key Insights

  • The problem requires finding a subarray of fixed length k with the maximum average.
  • The sliding window technique is an efficient way to handle this, as it allows us to compute the sum of elements in a window of size k without recomputing the sum from scratch for each subarray.
  • By maintaining a running sum of the last k elements, we can update the sum efficiently as we slide the window through the array.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The algorithm uses the sliding window approach to calculate the maximum average of contiguous subarrays of length k. We maintain a running sum of the first k elements and then slide the window across the array, updating the sum by subtracting the element that is left behind and adding the new element that comes into the window. The maximum average is then calculated by dividing the maximum sum by k.

Code Solutions

def findMaxAverage(nums, k):
    # Calculate the sum of the first 'k' elements
    max_sum = current_sum = sum(nums[:k])
    
    # Slide the window across the array
    for i in range(k, len(nums)):
        current_sum += nums[i] - nums[i - k]  # Update current sum
        max_sum = max(max_sum, current_sum)   # Update max sum if current is larger
    
    # Return the maximum average
    return max_sum / k
← Back to All Questions