The pattern here is the fixed-size sliding window. Because every window has the same length k, the average of a window and its sum are the same thing for comparison purposes — with k constant, the window with the largest sum is also the window with the largest average. So instead of dividing repeatedly, the whole problem becomes “find the maximum sum of any k consecutive elements.” The naive reading of that sentence — add up every group of k from scratch — throws away almost all its work, because a sliding window shares k - 1 of its elements with the previous one. The trick is to hold the running total and only adjust it by the single element that leaves and the single element that enters.
Brute Force: Recount Every Window
Time O(n·k)Space O(1)For each possible window start i, sum up the k elements from i to i + k - 1 and track the best sum seen so far. There are n - k + 1 windows in total, and each one is built from scratch.
class Solution: def findMaxAverage(self, nums: list[int], k: int) -> float: best = None for i in range(len(nums) - k + 1): window_sum = sum(nums[i : i + k]) if best is None or window_sum > best: best = window_sum return best / kWhy it is slow: there are n - k + 1 windows, and summing each takes k work, giving O(n·k) time. Consecutive windows overlap by k - 1 elements, so almost every element is added up over and over as the group slides — the recounting is the waste. Space is O(1) because we only keep one running best. This is wildly wasteful when n and k can both reach 10^5: n·k can be 10^10.
Sliding Window: Reuse the Running Sum
OptimalTime O(n)Space O(1)Seed the window by summing the first k elements once. Then, for each step, slide the window one position right and adjust the total in O(1): the element that leaves the left side is subtracted and the element that enters on the right is added. The window never leaves memory, so we never recount the k - 1 shared elements.
class Solution: def findMaxAverage(self, nums: list[int], k: int) -> float: window_sum = sum(nums[:k]) best = window_sum for start in range(1, len(nums) - k + 1): leaving_index = start - 1 entering_index = start + k - 1 window_sum += nums[entering_index] - nums[leaving_index] best = max(best, window_sum) return best / kTrace the file example, nums = [1, 12, -5, -6, 50, 3], k = 4 — seed once, then two O(1) slides:
a fixed-size window slides one cell right each step — drop the leftmost element, add the new rightmost one, and update the running sum in O(1) instead of recounting k elements
The first phase fills the window up to its fixed size k = 4 by successive adds. Start the running sum with the first element: 0 plus nums[0] = 1 gives 1. Every subsequent seed add is one statement, and the window keeps growing one slot at a time until it holds four elements.
Then the k = 1 edge case where the window is a single cell and there is nothing to slide:
a fixed-size window slides one cell right each step — drop the leftmost element, add the new rightmost one, and update the running sum in O(1) instead of recounting k elements
When k = 1 the window is a single cell, so seeding finishes immediately: the running sum is just 5 and that is also the best sum. There is no room to slide, because a length-1 window can only sit on the one element.
Why it is linear: the seed pass adds k elements, and each of the remaining n - k positions does exactly one add and one subtract — a constant amount of work per array element, for O(n) total time. Space is O(1) since only the running sum and the best sum are kept. Correctness rests on it measuring exactly the same n - k + 1 windows the brute force does: each slide moves the boundary by one index, so every k-length contiguous block is visited exactly once. The k = 1 case is handled naturally — the seed is the whole answer and the loop body never runs. Because best / k is only applied once at the very end, a single division error is far smaller than the allowed 10^-5 tolerance.