How hard is LeetCode 644. Maximum Average Subarray II?

LeetCode 644. Maximum Average Subarray II is rated Hard on LeetCode.

What is the time complexity of LeetCode 644. Maximum Average Subarray II?

The Python solution on this page runs in 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.

What is the space complexity of LeetCode 644. Maximum Average Subarray II?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 644. Maximum Average Subarray II cover?

LeetCode 644. Maximum Average Subarray II is tagged Array, Binary Search and Prefix Sum on LeetCode.

Is LeetCode 644. Maximum Average Subarray II a premium problem?

Yes. LeetCode 644. Maximum Average Subarray II is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Maximum Average Subarray II — LeetCode 644 Python Solution

HardLeetCode PremiumArrayBinary SearchPrefix Sum

Problem: #644
Pattern: Prefix Sum
Reading time: 5 min
Source: leetcode.com

The problem

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.

Example

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

Python solution

Python

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        def check(v: float) -> bool:
            s = sum(nums[:k]) - k * v
            if s >= 0:
                return True
            t = mi = 0
            for i in range(k, len(nums)):
                s += nums[i] - v
                t += nums[i - k] - v
                mi = min(mi, t)
                if s >= mi:
                    return True
            return False

        eps = 1e-5
        l, r = min(nums), max(nums)
        while r - l >= eps:
            mid = (l + r) / 2
            if check(mid):
                l = mid
            else:
                r = mid
        return l

Complexity

Measure	Complexity
Time	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
Space	O(1) auxiliary

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 644. Maximum Average Subarray II is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 644. Maximum Average Subarray II?: LeetCode 644. Maximum Average Subarray II is rated Hard on LeetCode.
What is the time complexity of LeetCode 644. Maximum Average Subarray II?: The Python solution on this page runs in 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.
What is the space complexity of LeetCode 644. Maximum Average Subarray II?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 644. Maximum Average Subarray II cover?: LeetCode 644. Maximum Average Subarray II is tagged Array, Binary Search and Prefix Sum on LeetCode.
Is LeetCode 644. Maximum Average Subarray II a premium problem?: Yes. LeetCode 644. Maximum Average Subarray II is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.