DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Maximum Average Subarray I

easySliding window

Problem statement

Given an integer array nums and an integer k (with 1 <= k <= len(nums)), look at every contiguous block of exactly k elements. Return the highest average among those blocks.

Answers within 1e-5 of the exact value are accepted.

Examples

Example 1

Input: nums = [4, -2, 7, 1, 0, 9], k = 2

Output: 4.5

Explanation: The pair sums are 2, 5, 8, 1, 9. The best is 0 + 9 = 9, and 9 / 2 = 4.5.

Example 2

Input: nums = [-3, -8, -1], k = 1

Output: -1.0

Explanation: With k = 1 each element is its own block, and -1 is the largest.

Hints

Approach

Use a fixed-size sliding window. Sum the first k elements once. Then move the window one step at a time: the new element on the right joins, the old element on the left drops out. Each move is one addition and one subtraction.

  1. window = sum(nums[0..k-1]), best = window.
  2. For i from k to n - 1: window += nums[i] - nums[i - k], then best = max(best, window).
  3. Return best / k.

Compare sums, not averages, and divide once at the end. That avoids floating-point work inside the loop.

ComplexityTime O(n)Space O(1)
Python
class Solution:
def findMaxAverage(self, nums: list[int], k: int) -> float:
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k] # add the new element, drop the old one
best = max(best, window)
return best / k

Follow-up questions

  • Return the start index of the best window as well as its average.
  • The data arrives as a stream. Keep the current k-sample average using a queue of the last k values.

Frequently asked questions

All the numbers can be negative. Starting at 0 would report an average that no block actually has, as in the [-3, -8, -1] example.

The sum of many large int values can overflow 32 bits. A long accumulator keeps the sum exact before the final division.

Moving averages over metrics: the busiest 5-minute stretch of request counts, or the worst 10-sample average of CPU on a host. Monitoring systems compute rolling windows the same way, by adding the new sample and dropping the oldest instead of re-summing.