LeetCode 643: Maximum Average Subarray I

A sliding window solution for finding the maximum average among all contiguous subarrays of fixed length k.

leetcodearraysliding-window

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

Item Meaning
Input Integer array nums and integer k
Output Maximum average of a contiguous subarray of length k
Constraint The subarray length must be exactly k

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:

Window Sum Average
[1, 12, -5, -6] 2 0.5
[12, -5, -6, 50] 51 12.75
[-5, -6, 50, 3] 42 10.5

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

Metric Value Why
Time O(n) Each element enters and leaves the window at most once
Space O(1) Only a few variables are stored

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:

Test Why
Official sample Checks normal sliding window behavior
Single element Minimum input
Negative single element Handles negative averages
k = 1 Best average is the maximum element
All negative values Must choose the least negative average
k = n Only one window exists