{x}
blog image

Maximum Average Subarray I

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.

 

Example 1:

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

Example 2:

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

 

Constraints:

  • n == nums.length
  • 1 <= k <= n <= 105
  • -104 <= nums[i] <= 104

Solution Explanation: Maximum Average Subarray I

This problem asks us to find the maximum average of a contiguous subarray of length k within a given array nums. A naive approach would involve calculating the average of every possible subarray of length k, which would have a time complexity of O(n*k), where n is the length of nums. However, a more efficient solution utilizes the sliding window technique to achieve a linear time complexity.

Sliding Window Approach:

  1. Initialization:

    • Calculate the sum of the first k elements in nums. This sum represents the sum of the first sliding window.
    • Initialize ans (the maximum average so far) to this initial sum.

  2. Sliding the Window:

    • Iterate through the array starting from the k-th element.
    • In each iteration:
      • Update the s (the sum of the current window) by subtracting the element that's leaving the window from the left and adding the new element entering the window from the right. This is done efficiently in O(1) time. s = s + nums[i] - nums[i - k]
      • Update ans by taking the maximum of ans and the current s.

  3. Return the Average:

    • After iterating through the entire array, divide ans by k to obtain the maximum average.

Time Complexity Analysis:

The sliding window approach iterates through the array only once. The sum calculation within the loop is O(1) because it only involves adding and subtracting a single element each time. Therefore, the overall time complexity is O(n), where n is the length of the input array nums.

Space Complexity Analysis:

The algorithm uses a few variables (ans, s, i) to store intermediate values. The space used is constant and independent of the input size. Therefore, the space complexity is O(1).

Code Examples (with explanations):

The provided code examples in multiple languages (Python, Java, C++, Go, TypeScript, Rust, and PHP) all implement the sliding window approach. Let's break down the Python example:

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        ans = s = sum(nums[:k]) # Initialize sum of first k elements and ans
        for i in range(k, len(nums)): #Iterate starting from kth element
            s += nums[i] - nums[i - k] #Efficiently update the window sum
            ans = max(ans, s) #Update ans with the maximum sum so far
        return ans / k # Return the maximum average

The other language examples follow the same logic, adapting the syntax and data structures to their respective languages. They all efficiently compute the maximum average subarray of length k in linear time.