Skip to main content
DSA patterns

Maximum Average Subarray I

easySliding windowDatadogSplunkDynatrace

Problem statement

You're given an array nums and a window size k. Look at every contiguous stretch of exactly k values in the array, and return the highest average any of those stretches has.

This is the same shape as scanning a metric — say, requests per second, or memory usage samples — for the busiest fixed-length window, such as "which 4-minute stretch had the highest average load".

Examples

Example 1

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

Output: 12.75000

Explanation: The window [12, -5, -6, 50] sums to 51, and 51 / 4 = 12.75, which is higher than the average of every other 4-element window in the array.

Example 2

Input: nums = [5], k = 1

Output: 5.00000

Explanation: With only one value and a window size of 1, the only possible window is [5], whose average is 5.

Hints

Hint 1: Recomputing the sum of every k-length window from scratch works, but it repeats a lot of the same additions between neighboring windows.

Approach

Optimal: Sliding window

Intuition

Two neighboring windows overlap almost completely — sliding the window one step to the right just drops the leftmost value and picks up one new value on the right. So instead of re-adding every value in each new window, start with the sum of the very first window, then slide: subtract the value that just fell out of the window, and add the value that just came in. That's one addition and one subtraction per step instead of k additions, which is what removes the extra factor of k from the brute force's time.

Steps

  1. Compute window_sum as the sum of the first k elements, and set best_sum = window_sum.
  2. For each later position i from k to n - 1:
    • Update window_sum += nums[i] - nums[i - k] (add the new element, remove the one that left the window).
    • Update best_sum if window_sum is larger.
  3. Return best_sum / k.

Dry run

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

step i window_sum best_sum
start — 1+12-5-6 = 2 2
slide 4 2 + 50 - 1 = 51 51
slide 5 51 + 3 - 12 = 42 51

The best sum found, 51, gives 51 / 4 = 12.75, matching the example.

Edge cases: when k equals the array's length, the loop that slides the window never runs (there's no i from k to n - 1), and the first window's sum is returned directly; when k is 1, sliding simply drops and re-adds one element at a time, which correctly reduces to tracking the running maximum single value.

Complexity

Time O(n) - the first window's sum takes O(k) to build, and after that each later window's sum is updated in O(1) time, for O(n) total instead of O(n · k) for the brute-force version.

Space O(1) - just one running sum and one running best, no matter how large the array or `k` is.

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


if __name__ == "__main__":
    print(f"{Solution().findMaxAverage([1, 12, -5, -6, 50, 3], 4):.5f}")  # 12.75000
    print(f"{Solution().findMaxAverage([5], 1):.5f}")  # 5.00000
RecapThe whole problem in a few lines, for the night before
  • Spot it: best average of any subarray of fixed length k
  • Idea: fixed sliding window: sum the first k, then slide by adding the new element and removing the one that left; track the max sum and divide by k once at the end
  • Cost: O(n) time, O(1) space
  • Trap: initialise the max with the first window, not 0, because all values can be negative

Interview follow-ups

  • What if you also needed the starting index of the best window, not just its average?

    Track one more variable — the starting index that produced best_sum — and update it alongside best_sum whenever a new window beats the current best. Still O(n) time and O(1) extra space.

  • What if k could be different on every query, against the same fixed nums?

    A prefix-sum array built once in O(n) time turns any single query's window sum into an O(1) lookup (prefix[i + k] - prefix[i]), so each query after that costs O(k) only to scan the starting positions for that query's k — or O(n) total per query if you check every starting position — rather than rebuilding a sliding-window sum from scratch each time. This trades a one-time O(n) setup cost for fast repeated queries.

Frequently asked questions

Dividing by k at every single window would do the same division n - k + 1 times, and division doesn't change which window has the largest sum — the window with the largest sum also has the largest average, since every window is the same size k. So it's simpler and just as correct to compare running sums the whole way through, and divide only once at the end.

Finding the busiest fixed-length window in a stream of metrics — the highest average requests-per-second over any 5-minute stretch, or the worst average latency over any 10-request run — is exactly this problem. It's also a common way interviewers check whether a candidate spots that a brute-force re-sum can become an O(1)-per-step slide, since that pattern (subtract what leaves, add what enters) comes up constantly in monitoring and rate-limiting code.

Because the window size k is fixed and given, not variable — each of the roughly n windows costs exactly k work to sum, giving n·k, whereas a true O(n²) problem is one where the work grows with the position rather than staying fixed at k. If k is close to n, that's close to O(n²); if k is small and fixed, the brute force is close to O(n).

Yes — the update rule window_sum += nums[i] - nums[i - k] is just arithmetic and doesn't care about sign. Negative values just make some windows' sums smaller (or negative), the same as they would if you recomputed each sum from scratch; the running-sum shortcut is still exactly correct, which the example (nums containing -5 and -6) already confirms.