Maximum Average Subarray I

Maximum Average Subarray I

What is this problem about?

The Maximum Average Subarray I problem provides an integer array and an integer k. Your task is to find a contiguous subarray of exactly length k that has the maximum average value, and return this maximum average. Because the length k is fixed, maximizing the average is mathematically identical to maximizing the sum of the subarray.

Why is this asked in interviews?

This is the textbook introduction to the Fixed-Size Sliding Window pattern. Interviewers use it as an early screening question to verify that a candidate knows how to avoid $O(N \times K)$ nested loops. It evaluates whether you can maintain a running sum dynamically by adding the incoming element and subtracting the outgoing element.

Algorithmic pattern used

This problem relies entirely on the Fixed-Size Sliding Window pattern.

1. Calculate the sum of the very first window (the first k elements). This is your initial current_sum and max_sum.
2. Slide the window one element to the right at a time. To do this efficiently, add the new element entering the window on the right (arr[i]), and subtract the old element leaving the window on the left (arr[i - k]).
3. Update max_sum = Math.max(max_sum, current_sum).
4. After traversing the array, return (double) max_sum / k.

Example explanation

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

1. Initial window [1, 12, -5, -6]. Sum = 2. max_sum = 2.
2. Slide right: add 50, remove 1. curr_sum = 2 + 50 - 1 = 51. max_sum = 51.
3. Slide right: add 3, remove 12. curr_sum = 51 + 3 - 12 = 42. max_sum = 51. End of array. The maximum sum is 51. The maximum average is $51 / 4 = 12.75$.

Common mistakes candidates make

A frequent mistake is calculating the average inside the loop and using max_avg = Math.max(max_avg, current_avg). While this works, performing floating-point division on every single iteration is computationally expensive and introduces unnecessary precision risks. It is far more optimal to simply track the maximum integer sum during the loop, and only perform the division by k exactly once at the very end.

Interview preparation tip

When solving fixed-window problems, the standard format is to build the initial window in a dedicated for loop from 0 to k-1. Then, create a second for loop starting from k to n-1 that does the sliding (add i, subtract i-k). This separation of "build" and "slide" logic makes the code highly readable and drastically reduces off-by-one index errors.