Maximum Average Subarray I

Easy#643fixed size

You get an array of numbers and a length k. Among all runs of k numbers in a row, find the largest average. Our example: [5, -3, 4, 8, -2, 6, -7] and k = 4 — the answer is 4: the run [4, 8, -2, 6] sums to 16, and 16 / 4 = 4.

643 Maximum Average Subarray IWalkthrough · 1×

Example: [5, -3, 4, 8, -2, 6, -7], k = 4. One loop does it all: the number at right comes in, the one at right - k goes out.

051-324384-2566-7sum0best–
not reached yetwindownumber coming innumber going outleft the windowbest window

Start with an empty window: sum = 0

01/38
restart · back · play · step
Speed
1function findMaxAverage(nums, k):
2 sum = 0
3 best = -infinity
4 for right from 0 to len(nums) - 1:
5 sum = sum + nums[right]
6 if right >= k:
7 sum = sum - nums[right - k]
8 if right >= k - 1:
9 best = max(best, sum)
10 return best / k
state
sum
0
best
–
right
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Next to each other, two windows share k - 1 numbers. So the new sum is the old one plus the number that came in minus the one that left: O(1) per step instead of adding k numbers again.
  2. All windows have the same length k, so the largest sum is the largest average. Comparing sums keeps the numbers whole, and the division happens once, at the end.
  3. best starts at -∞, not 0: if every number were negative, every sum would be below 0, and best = 0 would come out as a wrong answer.

Complexity

Time O(n): each number comes into the window once and leaves once. Memory O(1): only the sum, best and the index.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.