Maximum Average Subarray I

13 May 2026 0 Likes

Problem Description

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is exactly k and return the maximum average value among all possible subarrays of length k.

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: Subarray: [12,-5,-6,50]
Sum = 12 + (-5) + (-6) + 50 = 51
Average = 51 / 4 = 12.75

This becomes the maximum average among all subarrays of size 4.
Example 2:
Input: nums = [5], k = 1
Output: 5.00000
Explanation: The only subarray available is: [5]
Average = 5 / 1 = 5
Example 3:
Input: nums = [0,4,0,3,2], k = 1
Output: 4.00000
Explanation: When k = 1, every individual element forms a valid subarray.
The maximum value becomes: 4

Constraints

1. The array contains at least k elements.
2. The elements inside nums may be positive, negative, or zero.
3. The subarray considered must always have length exactly k.
4. The output should represent the maximum average among all valid subarrays.
5. Efficient solutions are expected to process the array in linear time.

Understanding the Problem

The problem is asking us to find a contiguous subarray of size k whose average value is maximum.

A straightforward way to understand the problem is by calculating the sum and average for every possible subarray of length k.

For example: nums = [1,12,-5,-6,50,3], k = 4. Possible subarrays of length 4 are:

[1,12,-5,-6]
Sum = 2
Average = 0.5

[12,-5,-6,50]
Sum = 51
Average = 12.75

[-5,-6,50,3]
Sum = 42
Average = 10.5

Among all averages, 12.75 is the maximum.

The main challenge is efficiently calculating sums for overlapping subarrays without recomputing everything repeatedly.

Hints

The first hint is to observe that consecutive subarrays of size k overlap heavily. Instead of recalculating the entire sum for every window, try reusing the previous window’s sum.

When the window moves forward:

1. Subtract the element leaving the window
2. Add the new element entering the window

This idea forms the basis of the sliding window technique, which helps achieve linear time complexity.

Solutions

OPTIMAL

Sliding Window Maximum Average Solution

This approach uses the sliding window technique to efficiently calculate the maximum average subarray of size k. Instead of recalculating the sum for every subarray from scratch, we reuse the previous window’s sum while moving through the array.

First, we calculate the sum of the initial window containing the first k elements. This becomes the starting window sum as well as the initial maximum sum.

After that, the window starts sliding one position at a time toward the right. Whenever the window moves:

1. The leftmost element is removed
2. The next right element is added

This allows the current window sum to be updated in constant time instead of recomputing the entire subarray sum repeatedly.

For example, if the current window is [1,12,-5,-6] and the next window becomes [12,-5,-6,50], then we simply subtract 1 and add 50.

This efficient update process continues until all windows are processed. Finally, the maximum sum found is divided by k to produce the maximum average value.
class Solution:

    def findMaxAverage(self, nums, k):

        n = len(nums)

        if n < k:
            return 0

        current_sum = sum(nums[:k])

        max_sum = current_sum

        left = 0
        right = k - 1

        while right < n - 1:

            right += 1

            current_sum = (
                current_sum
                + nums[right]
                - nums[left]
            )

            left += 1

            max_sum = max(
                max_sum,
                current_sum
            )

        return max_sum / k
public class A_SlidingWindow {
    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        int currentSum = 0;
        if (n < k)
            return 0;
        int left = 0, right = k - 1;

        for (int i = left; i <= right; i++) {
            currentSum += nums[i];
        }
        int maxSum = currentSum;

        while (right < n - 1) {
            currentSum = currentSum + (nums[++right] - nums[left++]);
            maxSum = Math.max(maxSum, currentSum);
        }

        return (double) maxSum / k;
    }
}
Time Complexity
O(n)
Space Complexity
O(1)

Conclusion

The Maximum Average Subarray I problem is an important introductory problem for understanding the sliding window technique. The problem demonstrates how overlapping computations can be reused efficiently instead of recalculating values repeatedly.

Mastering this problem helps build a strong understanding of window-based traversal, running sum optimization, and efficient array processing, which are frequently used in coding interviews and real-world applications.

💬 Comments