Maximum Average Subarray II - Video Solutions

Problem Overview: Given an integer array nums and an integer k, find the maximum possible average of any contiguous subarray whose length is at least k. The answer must be computed with high precision, which makes direct enumeration inefficient for large arrays.

Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)

Check every possible subarray of length at least k. Use two nested loops to choose a start and end index, then compute the average by iterating through the elements of that subarray. Track the maximum average encountered. This approach demonstrates the problem definition clearly but performs up to O(n^3) operations because each candidate range requires summing its elements again. It becomes infeasible once the array size grows.

Approach 2: Prefix Sum Optimization (O(n^2) time, O(n) space)

Use a prefix sum array where prefix[i] stores the sum of the first i elements. The sum of any subarray [l, r] can then be computed in constant time using prefix[r+1] - prefix[l]. Iterate over all start indices and expand the end index ensuring the length is at least k, computing averages quickly with the prefix array. This removes the inner summation loop and reduces complexity to O(n^2). It is still too slow for large inputs but introduces the key technique of prefix sum.

Approach 3: Binary Search on Answer + Prefix Sum (O(n logR) time, O(n) space)

The key observation: instead of directly searching for the maximum average, binary search the answer. Assume a candidate average mid. Transform the array by subtracting mid from every value. The problem becomes checking whether a subarray of length ≥ k has a sum ≥ 0. If such a subarray exists, the real maximum average is at least mid.

Use prefix sums to track cumulative values after the transformation. While iterating, maintain the minimum prefix sum seen before index i-k. If currentPrefix - minPrefix ≥ 0, a valid subarray exists. This check runs in O(n). Combine it with binary search over the numeric range of possible averages to reach O(n logR). This method relies on concepts from binary search and array processing.

Recommended for interviews: Interviewers expect the binary search on answer approach. Brute force and prefix sum solutions show that you understand the subarray structure, but the optimized solution demonstrates the ability to transform a numeric optimization problem into a feasibility check using binary search and prefix sums.