Maximum Average Subarray I (LeetCode 643)

The problem

You get an integer array nums and an integer k. Among all contiguous subarrays of length exactly k, find the one with the largest average and return that average.

Input:  nums = [1, 12, -5, -6, 50, 3], k = 4
Output: 12.75

The window [12, -5, -6, 50] sums to 51, and 51 / 4 = 12.75 is the best average.

How to think about it

Start with brute force. For every start index, add up the next k numbers and compare. There are about n windows and each costs k additions, so O(n·k). With n = 10⁵ and k = 5·10⁴, that’s billions of operations.

Notice the overlap. Two neighbouring windows share k − 1 elements. Recomputing those from scratch is wasted work.

The key insight: slide, don’t recompute. Moving the window one step right adds one element on the right and drops one on the left. So keep a running sum s, and on each step do s += nums[i] - nums[i-k]. That’s O(1) per step.

Compare sums, not averages. All windows have the same length k, so the largest sum gives the largest average. Divide once at the end. This avoids floating-point work inside the loop.

Which pattern is this? A fixed-size sliding window. The tell is “contiguous subarray of length exactly k”.

Approach

1. Sum the first k numbers into s, and set best = s.
2. For each i from k to the end, update s += nums[i] - nums[i-k].
3. Update best = max(best, s).
4. Return best / k.

Solution

def find_max_average(nums, k):
    s = sum(nums[:k]); best = s                       # first window
    for i in range(k, len(nums)):
        s += nums[i] - nums[i-k]; best = max(best, s) # add incoming, drop outgoing
    return best / k
# find_max_average([1,12,-5,-6,50,3], 4) -> 12.75

Dry run

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

The answer is 51 / 4 = 12.75.

Complexity

• Time: O(n). O(k) for the first sum, then O(1) for each of the remaining n − k steps.
• Space: O(1). A running sum and a best value. (nums[:k] makes a short copy; sum(nums[i] for i in range(k)) avoids it if you care.)

Edge cases and pitfalls

• k == len(nums): the loop doesn’t run, and the answer is the whole array’s average.
• All negative numbers: start best from the first window’s sum, not from 0, or you’ll return 0 by mistake.
• Off-by-one on the outgoing index. The element leaving is nums[i-k], not nums[i-k-1].
• Dividing inside the loop is correct but slower and invites floating-point noise. Compare integer sums.
• Integer division. In Python 3, / gives a float; in Java or C++, cast before dividing.

Related problems

• Permutation in String (LeetCode 567): a fixed-size window that tracks character counts instead of a sum.
• Sliding Window Maximum (LeetCode 239): a fixed window where the tracked value (the max) can’t be updated by simple add/subtract.
• Range Sum Query - Immutable (LeetCode 303): prefix sums, the other standard way to get any window’s sum in O(1).