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.

Description Solution Video 1:30:00

644. Maximum Average Subarray II

Hard37.7% acceptance1 companyPremium elsewhere, free here

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 <= 10⁴
-10⁴ <= nums[i] <= 10⁴

Asked at 1 company

Google

Topics

1:30:00

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

644. Maximum Average Subarray II

Asked at 1 company

Topics

Similar problems