LeetCode 643: Maximum Average Subarray I

Problem Restatement

We are given an integer array nums and an integer k.

We need to find a contiguous subarray whose length is exactly k and has the maximum average value.

Return that maximum average.

The answer is accepted if its error is less than 10^-5. The subarray must be contiguous and must have length exactly k.

Input and Output

Example function shape:

def findMaxAverage(nums: list[int], k: int) -> float:
    ...

Examples

Example 1:

nums = [1, 12, -5, -6, 50, 3]
k = 4

The possible windows of length 4 are:

The maximum average is:

12.75

Example 2:

nums = [5]
k = 1

The only subarray is [5].

So the answer is:

5.0

First Thought: Compute Every Window Sum From Scratch

A direct approach is to try every subarray of length k.

For each starting index, compute the sum of the next k numbers.

class Solution:
    def findMaxAverage(self, nums: list[int], k: int) -> float:
        best_sum = float("-inf")

        for start in range(len(nums) - k + 1):
            current_sum = 0

            for i in range(start, start + k):
                current_sum += nums[i]

            best_sum = max(best_sum, current_sum)

        return best_sum / k

This is correct, but it repeats too much work.

Adjacent windows share most of their elements.

For example:

[1, 12, -5, -6]
[12, -5, -6, 50]

The second window removes 1 and adds 50.

We do not need to recompute the whole sum.

Key Insight

Since every valid subarray has the same length k, maximizing the average is the same as maximizing the sum.

So we only need to find the maximum sum of any window of length k.

When the window slides one step to the right:

old window: nums[i-k], ..., nums[i-1]
new window: nums[i-k+1], ..., nums[i]

The new sum is:

new_sum = old_sum - nums[i - k] + nums[i]

This gives an O(n) solution.

Algorithm

1. Compute the sum of the first k elements.
2. Store it as both current_sum and best_sum.
3. Iterate from index k to the end of the array.
4. For each new index:
   1. Add nums[i].
   2. Remove nums[i - k].
   3. Update best_sum.
5. Return best_sum / k.

Implementation

class Solution:
    def findMaxAverage(self, nums: list[int], k: int) -> float:
        current_sum = sum(nums[:k])
        best_sum = current_sum

        for i in range(k, len(nums)):
            current_sum += nums[i]
            current_sum -= nums[i - k]

            best_sum = max(best_sum, current_sum)

        return best_sum / k

Code Explanation

We start by computing the first full window:

current_sum = sum(nums[:k])
best_sum = current_sum

Then each loop step slides the window by one position:

current_sum += nums[i]
current_sum -= nums[i - k]

The value nums[i] enters the window.

The value nums[i - k] leaves the window.

After updating the window sum, we update the best sum:

best_sum = max(best_sum, current_sum)

Finally:

return best_sum / k

returns the maximum average.

Correctness

The first window sum is computed exactly for nums[0:k].

For every later index i, the algorithm transforms the previous window sum into the next window sum by adding the new rightmost element and removing the old leftmost element. Therefore, current_sum is always the sum of the current contiguous subarray of length k.

The algorithm compares every such window sum with best_sum, so after all windows are processed, best_sum is the maximum sum among all contiguous subarrays of length k.

Because all valid subarrays have the same length k, the subarray with maximum sum also has maximum average. Therefore, best_sum / k is the correct answer.

Complexity

Testing

def run_tests():
    s = Solution()

    assert abs(s.findMaxAverage([1, 12, -5, -6, 50, 3], 4) - 12.75) < 1e-5
    assert abs(s.findMaxAverage([5], 1) - 5.0) < 1e-5
    assert abs(s.findMaxAverage([-1], 1) - (-1.0)) < 1e-5
    assert abs(s.findMaxAverage([0, 4, 0, 3, 2], 1) - 4.0) < 1e-5
    assert abs(s.findMaxAverage([-5, -2, -3, -4], 2) - (-2.5)) < 1e-5
    assert abs(s.findMaxAverage([10, 10, 10], 3) - 10.0) < 1e-5

    print("all tests passed")

run_tests()

Test meaning: