Skip to main content
Talentd

Maximum Average Subarray II - Solution & Explanation

HardPremiumFree on FleetCodeArrayBinary SearchPrefix Sum19 min readAsked at: Google
Practice this problem

Problem Statement

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

Find a contiguous subarray whose length is greater than or 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.

 

Example 1:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation:
- When the length is 4, averages are [0.5, 12.75, 10.5] and the maximum average is 12.75
- When the length is 5, averages are [10.4, 10.8] and the maximum average is 10.8
- When the length is 6, averages are [9.16667] and the maximum average is 9.16667
The maximum average is when we choose a subarray of length 4 (i.e., the sub array [12, -5, -6, 50]) which has the max average 12.75, so we return 12.75
Note that we do not consider the subarrays of length < 4.

Example 2:

Input: nums = [5], k = 1
Output: 5.00000

 

Constraints:

  • n == nums.length
  • 1 <= k <= n <= 104
  • -104 <= nums[i] <= 104

Approach Overview

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.

Solution

We note that if the average value of a subarray with length greater than or equal to k is v, then the maximum average number must be greater than or equal to v, otherwise the maximum average number must be less than v. Therefore, we can use binary search to find the maximum average number.

What are the left and right boundaries of binary search? The left boundary l must be the minimum value in the array, and the right boundary r is the maximum value in the array. Next, we binary search the midpoint mid, and judge whether there exists a subarray with length greater than or equal to k whose average value is greater than or equal to mid. If it exists, then we update the left boundary l to mid, otherwise we update the right boundary r to mid. When the difference between the left and right boundaries is less than a very small non-negative number, i.e., r - l < \epsilon, we can get the maximum average number, where \epsilon represents a very small positive number, which can be 10^{-5}.

The key to the problem is how to judge whether the average value of a subarray with length greater than or equal to k is greater than or equal to v.

We assume that in the array nums, there is a subarray with length j, the elements are a_1, a_2, cdots, a_j, and its average value is greater than or equal to v, i.e.,

$ \frac{a_1 + a_2 + cdots + a_j}{j} geq v

Then,

a_1 + a_2 + cdots + a_j geq v times j

That is,

(a_1 - v) + (a_2 - v) + cdots + (a_j - v) geq 0

We can find that if we subtract v from each element in the array nums, the original problem is transformed into a problem of whether the sum of the elements of a subarray with length greater than or equal to k is greater than or equal to 0. We can use a sliding window to solve this problem.

First, we calculate the sum s of the differences between the first k elements and v. If s geq 0, it means that there exists a subarray with length greater than or equal to k whose element sum is greater than or equal to 0.

Otherwise, we continue to traverse the element nums[j]. Suppose the current sum of the differences between the first j elements and v is s_j. Then we can maintain the minimum value mi of the sum of the differences between the prefix sum and v in the range [0,..j-k]. If s_j geq mi exists, it means that there exists a subarray with length greater than or equal to k whose element sum is greater than or equal to 0, and we return true.

Otherwise, we continue to traverse the element nums[j] until the entire array is traversed.

The time complexity is O(n times log M), where n and M are the length of the array nums and the difference between the maximum and minimum values in the array, respectively. The space complexity is O(1)$.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n^3)O(1)Conceptual understanding of the problem; very small arrays
Prefix Sum OptimizationO(n^2)O(n)When improving brute force using fast subarray sum queries
Binary Search + Prefix SumO(n logR)O(n)Optimal solution for large arrays and typical interview expectations

Video Solution

644. Maximum Average Subarray II (Leetcode Hard) • Programming Live with Larry • 697 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Maximum Average Subarray II easy or hard?
Maximum Average Subarray II is classified as Hard because it requires recognizing the binary-search-on-answer pattern. The transformation step—subtracting the candidate average and checking prefix sums—is not obvious without experience with advanced optimization problems.
Maximum Average Subarray II Python/Java solution
Most implementations follow the same structure across languages: binary search over the average range and a helper function that checks feasibility using prefix sums. The logic is identical in Python, Java, C++, Go, and TypeScript with only syntax differences.
How to solve Maximum Average Subarray II in O(n)?
A single pass solution is not possible because the answer depends on a continuous numeric range. Instead, combine O(n) feasibility checks with binary search on the average value. Each iteration verifies whether a transformed array contains a subarray of length ≥ k with sum ≥ 0.
What is the best approach for Maximum Average Subarray II?
The optimal approach uses binary search on the possible average combined with prefix sums. For a candidate average, subtract it from each element and check whether a subarray of length at least k has a non‑negative sum. This feasibility check runs in O(n), and binary search over the value range gives an overall complexity of O(n logR).
Is Maximum Average Subarray II asked at Google/Amazon/Meta?
This problem represents a common interview pattern used by companies like Google, Amazon, and Meta when testing advanced binary search techniques. It evaluates whether candidates can apply binary search on the answer and combine it with prefix sum reasoning.
What data structure is used in Maximum Average Subarray II?
The main structure is an array with prefix sum tracking. The algorithm maintains running prefix sums and the minimum prefix value seen so far to determine whether a valid subarray exists during the binary search check.
What is the time complexity of Maximum Average Subarray II?
The optimal binary search solution runs in O(n logR) time where n is the array length and R is the numeric range of possible averages. Each binary search step performs a linear scan using prefix sums to verify whether a valid subarray exists. Space complexity is O(n) for prefix tracking.

Ready to solve this problem?

Practice Maximum Average Subarray II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Average Subarray I