Maximum Average Subarray I

Explanation & Solution

Description

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.

Input:nums = [1,12,-5,-6,50,3], k = 4

-5

-6

Output: 12.75

Explanation: The subarray [12,-5,-6,50] has the maximum average 51 / 4 = 12.75.

Constraints

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

Approach

Sliding Window pattern

1. Compute the Initial Window Sum

Calculate the sum of the first k elements.
This is our starting window and initial maxSum.

2. Slide the Window Across the Array

For each new position, add the element entering the window on the right and subtract the element leaving the window on the left.
This maintains the running sum in O(1) per step instead of recomputing the sum from scratch.

3. Track the Maximum Sum

After each slide, compare the current window sum with maxSum and update if larger.
The maximum average corresponds to the maximum sum since all windows have the same length k.

4. Return the Average

Divide maxSum by k to get the maximum average.

Key Insight

This is a fixed-size sliding window pattern. Since the window size never changes, we never need to shrink or expand — we simply slide by adding one element and removing one element at each step. The key optimization is maintaining a running sum rather than recalculating the sum of k elements at every position.

Time

O(n)we visit each element exactly once.

Space

O(1)only a few variables are used.

Visualization

Input:

[1, 12, -5, -6, 50, 3], k = 4

—

Press ▶ or use ← → to step through

Left (L)Right (R)WindowDone

4 steps

Solution Code

Minimum Size Subarray Sum