EasyArraySliding Window

Maximum Average Subarray I

1 approach, code in every language

You are given an array of integers and a fixed length k. Consider every contiguous block of exactly k consecutive elements and compute the average of each block.

Return the largest average found among all such blocks. Answers within a tiny numerical tolerance of the true maximum are accepted.

Example 1

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, which beats every other length-4 window.

Example 2

Input: nums = [4, 0, 4], k = 2

Output: 2.00000

The two length-2 windows are [4, 0] and [0, 4], both averaging 2. The maximum average is 2.

Constraints

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

Fixed-Size Sliding Window

Maintain the sum of a k-length window, slide it one step at a time, and track the largest sum seen.

Loading animation…

Intuition

Every candidate block has the same length k, so comparing averages is the same as comparing their sums. Rather than recomputing each window's sum from scratch, we compute the first window once and then slide: each shift adds the incoming element on the right and drops the outgoing element on the left. That keeps every update constant time, so a single left-to-right pass reveals the largest window sum. Dividing that best sum by k at the end converts it to the maximum average.

Algorithm walkthrough

1Add the first k elements to form the initial window sum and treat it as the current best.
2Slide the window right by one: add nums[i] and subtract nums[i - k].
3After each slide, update the best sum if the new window sum is larger.
4Continue until the window reaches the end of the array.
5Divide the best sum by k and return it as a floating-point average.

Implementation

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        window_sum = sum(nums[:k])
        best = window_sum
        for i in range(k, len(nums)):
            window_sum += nums[i] - nums[i - k]
            best = max(best, window_sum)
        return best / k

Time

O(n)

Space

O(1)

A single pass with constant-time window updates; no extra storage beyond a few counters.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Search

After the pattern

Now solve one you haven't seen.

Warmest Run of Days is our own problem on the technique behind Maximum Average Subarray I: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free