Maximum Average Subarray II

Maximum Average Subarray II

What is this problem about?

The Maximum Average Subarray II problem is the advanced version of Part I. You are given an array of integers and an integer k. This time, you must find a contiguous subarray whose length is greater than or equal to k that has the maximum average value. You must return this maximum average with an acceptable error margin of $10^{-5}$.

Why is this asked in interviews?

This is a Hard-level problem that completely breaks the standard sliding window approach because the window size is variable ($L \ge k$). Interviewers ask it to test a candidate's mastery of Binary Search on the Answer. It evaluates whether you can combine floating-point binary search with Prefix Sum math to validate an abstract statistical guess in $O(N)$ time.

Algorithmic pattern used

This problem leverages Binary Search on the Answer and Prefix Sums.

1. Define a search space for the average: low = min(array), high = max(array).
2. Guess an average mid.
3. To check if an average of mid is possible for a length $\ge k$, we subtract mid from every element in the array. Now, we just need to find any subarray of length $\ge k$ that has a sum $\ge 0$.
4. We maintain a running prefix sum of this shifted array. To maximize the subarray sum ending at i, we subtract the minimum prefix sum seen so far (from index $0$ to $i-k$). If this difference is $\ge 0$, the guess mid is valid! Adjust low = mid. Else high = mid.

Example explanation

Array: [1, 12, -5, -6, 50, 3], k = 4. Guess mid = 10. Subtract 10 from all elements. Shifted: [-9, 2, -15, -16, 40, -7]. We need a subarray $\ge$ length 4 with sum $\ge 0$. Prefix sums:

• i=0: -9
• i=1: -7
• i=2: -22
• i=3: -38. Length is 4. Sum is -38. Valid? No. min_prev_sum tracks prefix at i-k. min_prev_sum = 0.
• i=4: 2. min_prev_sum updates with prefix at idx 0 (-9). min_prev_sum = -9. Current prefix is 2. Best subarray ending here has sum 2 - (-9) = 11. $11 \ge 0$! We found a subarray of length 5 [12, -5, -6, 50] whose average is $> 10$. We can search higher.

Common mistakes candidates make

A major pitfall is trying to track all possible window sizes using nested loops, which results in $O(N^2)$ and a Time Limit Exceeded error. Another mistake is in the binary search loop condition. Because we are searching for a double, using while (low <= high) will cause an infinite loop due to floating-point precision. You must use an error margin like while (high - low > 1e-5) to terminate correctly.

Interview preparation tip

The key to the Maximum Average Subarray II coding problem is the mathematical shift. If you want to know if an array A has an average $\ge M$, it is mathematically identical to checking if sum(A[i] - M) >= 0. This brilliantly removes division from the inner loop, turning an average problem into a much simpler prefix-sum problem.