[/dsa/leetcode]

643 - Maximum Average Subarray I

Wednesday, 16 September 2026

<easy> [problem]

The fixed size sliding window - consecutive windows share k-1 elements, so each step is one add and one subtract instead of a rescan.

{array}{sliding window}

Problem

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10^-5 will be accepted.

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Input: nums = [5], k = 1
Output: 5.00000

Constraints:

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

Approach

The window length is fixed, so dividing by k is the same operation for every candidate and cannot change which one is largest. Maximum average is maximum sum, and the division happens once at the end — no floating point anywhere in the loop, so there is nothing to lose precision on and nothing to compare with an epsilon.

Summing each of the n - k + 1 windows from scratch is O(n·k). But consecutive windows overlap in k - 1 elements, and recomputing that shared part is the only wasted work. Slide instead: one element enters at the right, one leaves at the left.

[1, 12, -5, -6] 50  3        sum = 2
 1 [12, -5, -6, 50] 3        sum = 2 - 1 + 50 = 51
 1  12 [-5, -6, 50, 3]       sum = 51 - 12 + 3 = 42
                             max = 51  ->  51 / 4 = 12.75

Sliding Window

Build the first window with accumulate, then every later window is one += away. Indexing by the entering element makes the loop bounds fall out: window ending at i starts at i - k + 1, so the element dropping out is nums[i - k].

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        const int n = nums.size();
        int sum = accumulate(nums.begin(), nums.begin() + k, 0);
        int maxi = sum;
        for (int i = k; i < n; i++) {
            sum += nums[i] - nums[i - k];
            maxi = max(maxi, sum);
        }
        return maxi / (double)k;
    }
};

maxi is seeded with the first window rather than something like 0 or INT_MIN. Seeding with 0 is wrong on all-negative input, and there is no need for a sentinel when a real answer is already in hand.

  • time: O(n) — k for the first window, then one step per remaining element
  • space: O(1) — two ints

Does the sum overflow?

Worth actually checking rather than reaching for long long by reflex. The largest magnitude a window sum can reach is n · max|nums[i]| = 10^5 · 10^4 = 10^9, and INT_MAX is about 2.147 · 10^9. So int fits with room to spare, in both directions. The 0 literal seeding accumulate matters here for the same reason — it fixes the accumulator type, and 0 makes it int.

Change the constraints slightly and that answer flips, which is the point: the bound is a fact about this problem, not about the technique.

Avoid unsigned arithmetic in the bound

A natural way to write the loop is over the leaving element, for (int i = 0; i < nums.size() - k; i++). That works here, but nums.size() is a size_t, so the subtraction is unsigned — if k ever exceeded n it would wrap to an enormous value instead of going negative, and the loop would run straight off the array. The constraints rule that out, but hoisting const int n = nums.size(); and iterating over the entering element avoids the trap entirely.

This is the easy half of the sliding window family. The fixed size version never has to decide how big the window is; the variable size version grows the right edge and shrinks the left while some condition is violated. See the sliding window note for both.

quantinium © 2026