Maximum Average Subarray I

Difficulty: Easy | Acceptance: 47.70% | Paid: No Topics: Array, Sliding Window

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⁻⁵ will be accepted.

• Examples
• Constraints
• Brute Force
• Sliding Window

Examples

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

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

Constraints

- n == nums.length
- 1 <= k <= n <= 10^5
- -10^4 <= nums[i] <= 10^4

Brute Force

Intuition Check every possible subarray of length k, calculate its sum, and keep track of the maximum sum found.

Steps

• Initialize max_sum to a very small number (e.g., negative infinity).
• Iterate through the array from index 0 to n - k.
• For each starting index i, calculate the sum of the next k elements.
• Update max_sum if the current sum is greater.
• Finally, return max_sum / k.

class Solution:
    def findMaxAverage(self, nums: list[int], k: int) -> float:
        n = len(nums)
        max_sum = float('-inf')
        for i in range(n - k + 1):
            current_sum = 0
            for j in range(i, i + k):
                current_sum += nums[j]
            if current_sum > max_sum:
                max_sum = current_sum
        return max_sum / k

Complexity

• Time: O(n * k)
• Space: O(1)
• Notes: Simple but inefficient for large inputs.

Sliding Window

Intuition Instead of recalculating the sum for every subarray, reuse the sum of the previous window by subtracting the element leaving the window and adding the element entering it.

Steps

• Calculate the sum of the first k elements and store it as current_sum and max_sum.
• Iterate from index k to the end of the array.
• Update current_sum by adding nums[i] and subtracting nums[i - k].
• Update max_sum if current_sum is greater.
• Return max_sum / k.

class Solution:
    def findMaxAverage(self, nums: list[int], k: int) -> float:
        n = len(nums)
        current_sum = sum(nums[:k])
        max_sum = current_sum
        for i in range(k, n):
            current_sum += nums[i] - nums[i - k]
            if current_sum > max_sum:
                max_sum = current_sum
        return max_sum / k

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Optimal solution for this problem.