LeetCode 643 - Maximum Average Subarray I

LeetCode Problem 643

Difficulty: 🟢 Easy
Topics: Array, Sliding Window

Solution

Problem Understanding

The problem asks us to find the maximum average value among all contiguous subarrays of a fixed length k.

In other words, given an integer array nums, we must examine every possible subarray whose size is exactly k, compute its average, and return the largest average found.

A key detail is that the subarray must be contiguous, meaning its elements appear next to each other in the original array. We cannot skip elements or rearrange them.

For example, if:

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

the valid subarrays of length 4 are:

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

We compute the average for each one and return the maximum.

The input consists of:

• nums, an integer array of length n
• k, the exact length of the subarray we must consider

The expected output is a floating-point number representing the maximum average among all valid subarrays.

The constraints are important:

• 1 <= k <= n <= 10^5
• -10^4 <= nums[i] <= 10^4

Since n can be as large as 100,000, an inefficient solution that repeatedly recomputes sums for overlapping subarrays will likely be too slow. We need an algorithm that scales efficiently.

Several edge cases are guaranteed to be valid by the problem constraints:

• k is always at least 1, so there is always a valid subarray.
• k can equal n, meaning the only possible subarray is the entire array.
• Values may be negative, meaning the maximum average could also be negative.
• Arrays can contain only one element.

A naive implementation may become inefficient because consecutive windows overlap heavily. Recomputing sums from scratch for every subarray would repeat a lot of work.

Approaches

Brute Force Approach

The most straightforward solution is to examine every contiguous subarray of size k.

For each starting position, we compute the sum of the next k elements, divide by k, and track the largest average encountered.

This approach is correct because it explicitly checks every valid candidate subarray. Since the answer must come from one of these windows, comparing all of them guarantees correctness.

However, the issue is performance. If we recompute the sum for each window independently, every subarray requires O(k) work.

There are roughly n - k + 1 windows, so the total complexity becomes:

O((n - k + 1) × k) ≈ O(nk)

In the worst case, when both n and k are close to 10^5, this becomes far too slow.

Optimal Approach, Sliding Window

The key observation is that adjacent subarrays of length k overlap almost completely.

For example:

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

The second window differs from the first by only:

• removing the leftmost element (1)
• adding the new rightmost element (50)

Instead of recomputing the entire sum, we can update the previous window sum efficiently:

new_sum = old_sum - outgoing + incoming

This is the essence of the sliding window technique.

We first compute the sum of the initial window of size k. Then, as the window moves one step to the right, we subtract the element leaving the window and add the new element entering it.

This reduces each transition to constant time, making the entire algorithm linear.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(nk)	O(1)	Recomputes each window sum independently
Optimal	O(n)	O(1)	Uses a sliding window to update sums incrementally

Algorithm Walkthrough

Optimal Sliding Window Algorithm

1. Compute the sum of the first k elements.

This gives us the sum of the first valid subarray. Since every candidate subarray has length k, this provides our starting point. 2. Initialize a variable to track the maximum window sum.

We store the first window sum as the initial maximum because it is already a valid candidate. 3. Start sliding the window from index k to the end of the array.

At every step, the window moves one position to the right. 4. Update the current window sum.

Remove the element that leaves the window and add the new element entering it:

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

This works because the window size stays fixed. 5. Update the maximum sum if needed.

If the current window sum exceeds the best seen so far, update the maximum. 6. Return the maximum average.

Since every window has length k, the maximum average is:

max_sum / k

Why it works

The algorithm maintains an invariant:

current_sum always represents the exact sum of the current window of length k.

We establish this invariant by computing the first window sum correctly. Every subsequent update removes the outgoing element and adds the incoming one, preserving correctness.

Since the algorithm evaluates every valid subarray exactly once and tracks the maximum sum, the final result must correspond to the maximum average subarray.

Python Solution

from typing import List

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

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

            max_sum = max(max_sum, current_sum)

        return max_sum / k

The implementation begins by computing the sum of the first k elements. This forms the initial sliding window and establishes the baseline maximum sum.

We then iterate from index k onward. At each step, the window shifts one position to the right. Instead of recalculating the sum from scratch, we incrementally update it by adding the new element and subtracting the element that falls out of the window.

The variable max_sum keeps track of the best window sum encountered so far. Since every window has the same size k, comparing sums is equivalent to comparing averages.

Finally, we divide the maximum sum by k to return the maximum average.

Go Solution

func findMaxAverage(nums []int, k int) float64 {
	currentSum := 0

	for i := 0; i < k; i++ {
		currentSum += nums[i]
	}

	maxSum := currentSum

	for right := k; right < len(nums); right++ {
		currentSum += nums[right]
		currentSum -= nums[right-k]

		if currentSum > maxSum {
			maxSum = currentSum
		}
	}

	return float64(maxSum) / float64(k)
}

The Go implementation follows the same logic as the Python version.

One Go-specific detail is explicit type conversion when returning the result. Since integer division would truncate decimals, both maxSum and k are converted to float64 before division.

There is no need to handle nil or empty slices separately because the constraints guarantee:

1 <= k <= n

which means the input is always valid and non-empty.

Worked Examples

Example 1

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

First window:

[1,12,-5,-6]
sum = 2
max_sum = 2

We now slide the window.

Step	Window	Calculation	Current Sum	Max Sum
Initial	[1,12,-5,-6]	1 + 12 - 5 - 6	2	2
1	[12,-5,-6,50]	2 - 1 + 50	51	51
2	[-5,-6,50,3]	51 - 12 + 3	42	51

Final answer:

51 / 4 = 12.75

Example 2

nums = [5]
k = 1

Initial window:

[5]
sum = 5
max_sum = 5

No sliding is needed because the array length equals k.

Final answer:

5 / 1 = 5.0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed at most twice, once entering the window and once leaving
Space	O(1)	Only a few variables are used regardless of input size

The algorithm runs in linear time because every array element participates in constant-time updates to the sliding window. No nested iteration is required.

The space complexity remains constant because we only store a few integers for tracking sums and indices, independent of input size.

Test Cases

solution = Solution()

assert abs(solution.findMaxAverage([1,12,-5,-6,50,3], 4) - 12.75) < 1e-5  # Provided example
assert abs(solution.findMaxAverage([5], 1) - 5.0) < 1e-5  # Single element array

assert abs(solution.findMaxAverage([1,2,3,4,5], 1) - 5.0) < 1e-5  # k = 1, max single value
assert abs(solution.findMaxAverage([1,2,3,4,5], 5) - 3.0) < 1e-5  # k = n, entire array

assert abs(solution.findMaxAverage([-1,-12,-5,-6], 2) - (-5.5)) < 1e-5  # All negative values

assert abs(solution.findMaxAverage([0,0,0,0], 2) - 0.0) < 1e-5  # All zeros

assert abs(solution.findMaxAverage([5,-10,15,-20,25], 2) - 2.5) < 1e-5  # Mixed positive/negative

assert abs(solution.findMaxAverage([10000,-10000,10000,-10000], 2) - 0.0) < 1e-5  # Extreme values

assert abs(solution.findMaxAverage([3,3,3,3], 2) - 3.0) < 1e-5  # Repeated values

Test	Why
[1,12,-5,-6,50,3], k=4	Validates the provided example
[5], k=1	Tests smallest valid input
[1,2,3,4,5], k=1	Ensures single-element windows work
[1,2,3,4,5], k=5	Validates full-array window
Negative-only array	Ensures algorithm handles negative averages
All zeros	Tests neutral values
Mixed positive and negative	Verifies window updates remain correct
Extreme values	Confirms handling of constraint boundaries
Repeated values	Ensures stable behavior with duplicates

Edge Cases

When k = 1

This case effectively asks for the largest individual element because every subarray contains exactly one number. A buggy implementation might overcomplicate this scenario, but the sliding window naturally handles it because each window contains one value and shifts normally.

When k = n

If the window size equals the array length, only one valid subarray exists, the entire array. Some implementations accidentally attempt to slide beyond bounds. Our implementation avoids this because the loop starts at k, and when k == len(nums), the loop never runs.

Arrays With Only Negative Numbers

Negative values can be tricky because the "maximum" average is still negative. A naive implementation that initializes the maximum to 0 would fail. Our solution initializes max_sum using the first valid window, ensuring correctness even when every value is negative.