Day 10 of 250: LeetCode 643 Maximum Average Subarray I | Fixed Window Sliding Explained

Coming Off Yesterday: From Global Boundaries to a Moving Frame

On Day 9, we solved Trapping Rain Water by thinking about global boundaries. For every index in the elevation map, we needed to know the tallest bar anywhere to its left and anywhere to its right. The answer could not be found by looking at neighbors; it required the full left and right context of the array, which is why we built two auxiliary arrays in separate passes.

Today the problem flips that thinking. We are not asking about global context. We are asking about a fixed-size frame that slides across the array, and we only care about what is inside the frame at any given moment. The insight is that when the window size is fixed, we do not need to recompute the sum inside the frame from scratch every time we move it. We just add the new element entering the frame on the right and subtract the element leaving on the left. One addition, one subtraction, one update. That is the sliding window technique in its purest form.

Day 10 is LeetCode 643: Maximum Average Subarray I. It is tagged Easy, and it is the canonical introduction to the fixed-size sliding window, a pattern that recurs in dozens of problems across all difficulty levels. Getting this one right, and understanding exactly why the sliding update is valid, builds the foundation for everything more complex that uses the same idea.

Problem Statement

You are given an integer array nums consisting of n elements and an integer k. Find a contiguous subarray of length exactly k that has the maximum average value, and return this value. Any answer with a calculation error less than 10^-5 will be accepted.

Example 1:

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

Example 2:

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

Constraints:

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

The Core Insight: A Fixed Window Slides, It Does Not Restart

Here is the observation that makes this problem O(n) instead of O(n × k): when two adjacent windows of size k overlap, they share k - 1 elements. The only difference between window [i, i+k-1] and window [i+1, i+k] is that one element leaves on the left and one element enters on the right. Everything in between is identical.

This means we can update the window sum in constant time. Instead of summing all k elements again after sliding, we do:

newSum = oldSum + nums[i] - nums[i - k]

This single line replaces what would otherwise be an inner loop. Across all n - k + 1 windows, the total work is O(n) instead of O(n × k).

The brute force approach computes the sum of each window independently:

// Brute force: O(n × k) time
for (let i = 0; i <= nums.length - k; i++) {
    let sum = 0;
    for (let j = i; j < i + k; j++) {
        sum += nums[j];
    }
    maxSum = Math.max(maxSum, sum);
}

For n = 10^5 and k = 10^4, this means up to 10^9 operations. The sliding window reduces that to a single pass of 10^5 operations. The constraint n <= 10^5 is a strong hint that O(n) is expected.

First Instincts vs. Correct Thinking

Most people's first instinct is the nested loop above. It generates every window and sums it. The logic is easy to follow, but the inner loop is the problem. Every time we slide the window by one position, we restart the summation from scratch even though k - 1 elements are shared with the previous window.

The mental shift is to ask: "What changes when I slide the window by one step?" The answer is exactly two things: one element is added on the right and one element is removed on the left. Nothing else changes. So instead of re-summing all k elements, we apply those two updates to the previous sum. This reuse of prior computation, avoiding redundant work by carrying state forward, is what defines the sliding window technique.

Notice that this problem has a fixed window size. Every candidate subarray is exactly k elements long. This is a key distinction from problems with variable window sizes (like maximum subarray with a target constraint), where the window can grow and shrink based on conditions. Fixed-size sliding windows are simpler because we always add exactly one and remove exactly one at each step.

Understanding the Approach

We split the algorithm into two phases.

In the first phase, we compute the sum of the first window: elements from index 0 to index k - 1. This is done with a simple loop over the first k elements. We store this in currSum and also set maxSum = currSum because the first window is the only one we have seen and is trivially the maximum so far.

In the second phase, we slide the window from index k to n - 1. At each position i, the new element entering the window is nums[i] and the element leaving the window is nums[i - k]. We update currSum in one step: currSum += nums[i] - nums[i - k]. If this new sum exceeds maxSum, we update maxSum.

After all windows have been processed, we divide maxSum by k to get the average and return it. We divide only once at the very end, not on every iteration, because dividing n - k + 1 times and comparing averages is equivalent to dividing once after comparing sums. Division is more expensive than comparison, so this is a small but meaningful optimization.

Deep Dry Run: Every Step Explained

We will trace through nums = [1, 12, -5, -6, 50, 3] with k = 4 completely.

Initial state:

nums  = [1, 12, -5, -6, 50, 3]
index =  0   1   2   3   4  5

k = 4
currSum = 0
maxSum  = (not yet set)

Phase 1: Compute the First Window Sum

Window: indices 0 through 3

[1]  [12]  [-5]  [-6]   50   3
 ^    ^     ^     ^
 |____|_____|_____|
      first window

currSum = 1 + 12 + (-5) + (-6) = 2
maxSum  = 2

The first window spans [1, 12, -5, -6] and sums to 2. This is our baseline.

Phase 2: Slide the Window

The loop starts at i = k = 4 and runs through i = n - 1 = 5.

Iteration 1 (i = 4):

1   [12]  [-5]  [-6]  [50]   3
      ^     ^     ^     ^
      |_____|_____|_____|
           window slides right

Element entering: nums[4]    = 50
Element leaving:  nums[4-4]  = nums[0] = 1

currSum = 2 + 50 - 1 = 51

51 > maxSum (2) → update maxSum.

currSum = 51
maxSum  = 51

The window shifts one step right. 50 joins and 1 leaves. The sum jumps from 2 to 51. New maximum.

Iteration 2 (i = 5):

1    12   [-5]  [-6]  [50]  [3]
             ^     ^     ^    ^
             |_____|_____|____|
                  window slides right

Element entering: nums[5]    = 3
Element leaving:  nums[5-4]  = nums[1] = 12

currSum = 51 + 3 - 12 = 42

42 < maxSum (51) → no update.

currSum = 42
maxSum  = 51

The window shifts again. 3 joins and 12 leaves. Sum drops from 51 to 42. No improvement.

End of loop. All windows of size 4 have been evaluated.

maxSum    = 51
maxAverage = 51 / 4 = 12.75

return 12.75000

Final output: 12.75000. Correct. The window [12, -5, -6, 50] gives the highest sum of 51 and average of 12.75.

Bonus trace for Example 2: nums = [5], k = 1

Only one element. Phase 1 sets currSum = 5, maxSum = 5. Phase 2 loop does not execute because k = n = 1 and there are no remaining indices. Return 5 / 1 = 5.00000. Correct.

What Made It Work: The Deeper Why

1. Adjacent windows of size k share exactly k - 1 elements. This is the mathematical justification for the sliding update. The sum of window [i+1, i+k] equals the sum of window [i, i+k-1] plus nums[i+k] minus nums[i]. Proving this to yourself algebraically makes the technique feel inevitable rather than clever.

2. Tracking the maximum sum and dividing once is equivalent to tracking the maximum average at every step. Since k is constant, maximizing sum / k is the same as maximizing sum. Comparing sums instead of averages avoids unnecessary floating point divisions on every iteration and reduces error accumulation, which matters given the 10^-5 precision constraint in the problem.

3. Each element is added exactly once and removed exactly once across the entire algorithm. In Phase 1, all k elements of the first window are added once. In Phase 2, each subsequent element is added once when its index i is reached and removed once when the window slides past it. Total operations across both phases: n additions and n - k subtractions. No element is touched more than twice.

4. The fixed window size removes all ambiguity about when to expand or contract. In variable-size sliding window problems, you need conditions to decide when to grow or shrink the window. Here, the window never changes size. It always has exactly k elements. This makes the sliding logic deterministic: one in, one out, every step.

The Code

var findMaxAverage = function(nums, k) {
    let currSum = 0;
    for (let i = 0; i < k; i++) {
        currSum += nums[i];
    }

    let maxSum = currSum;
    for (let i = k; i < nums.length; i++) {
        currSum += nums[i] - nums[i - k];
        if (currSum > maxSum) {
            maxSum = currSum;
        }
    }
    return maxSum / k;
};

The first for loop runs from i = 0 to i = k - 1 and computes the sum of the initial window. After this loop, currSum holds the sum of the first k elements.

We then set maxSum = currSum. This handles the edge case where k == n, meaning there is only one window. If the second loop never executes, maxSum already holds the correct answer.

The second for loop starts at i = k and runs to i = nums.length - 1. At each step, nums[i] is the element entering the window on the right and nums[i - k] is the element leaving the window on the left. We update currSum in a single expression by combining the addition and subtraction. This is cleaner and slightly faster than two separate lines.

The if (currSum > maxSum) check updates maxSum only when we find a larger window sum. We use a manual comparison rather than Math.max because it avoids a function call overhead in a tight inner loop, though either is correct.

Finally, we return maxSum / k. The division happens exactly once, after all comparisons are complete.

Complexity Analysis

Common Mistakes

Mistake 1: Starting the sliding loop at i = k - 1 instead of i = k.

If the loop starts at i = k - 1, the first sliding step removes nums[k - 1 - k] = nums[-1], which is out of bounds or wraps around depending on the language. The window element leaving the frame when entering index i is always nums[i - k], and this is only valid when i >= k.

// Wrong: loop starts one step too early
for (let i = k - 1; i < nums.length; i++) {
    currSum += nums[i] - nums[i - k]; // nums[i-k] is invalid when i = k-1
}

Mistake 2: Dividing inside the loop to compare averages.

Dividing by k on every iteration produces a correct answer but is unnecessary work. Since k is constant, the window with the maximum sum also has the maximum average. Computing and comparing floating point averages in a tight loop can also introduce rounding errors.

// Wasteful and potentially less precise
if ((currSum / k) > (maxSum / k)) { ... }
// Better: compare sums directly
if (currSum > maxSum) { ... }

Mistake 3: Recomputing the sum inside the sliding loop with a nested loop.

Some candidates correctly identify the sliding window pattern but then recompute the sum from scratch inside the second loop anyway, negating the entire benefit.

// Wrong: O(n × k) despite having a sliding loop structure
for (let i = k; i < nums.length; i++) {
    currSum = 0;
    for (let j = i - k + 1; j <= i; j++) { // re-summing from scratch
        currSum += nums[j];
    }
}

Always update currSum using the sliding formula: currSum += nums[i] - nums[i - k].

Mistake 4: Returning maxSum instead of maxSum / k.

The problem asks for the average, not the sum. Forgetting the final division returns a value that is k times too large. For Example 1, this would return 51 instead of 12.75.

Mistake 5: Initializing maxSum before computing the first window.

If you initialize maxSum = 0 or maxSum = -Infinity and then set it after the first loop, you introduce a risk: if all elements are negative, maxSum = 0 would be returned as the answer when the actual maximum average is negative. Initializing maxSum = currSum immediately after the first window sum is computed is the correct approach.

Interview Tips

Step 1: Name the brute force and its complexity before moving on. Say: "A naive approach loops over every window of size k and recomputes the sum each time. That is O(n × k). For n = 10^5 and k = 10^4, that is too slow."

Step 2: State the overlapping structure observation. Say: "Adjacent windows of size k share k - 1 elements. So I can slide from one window to the next by adding one new element and removing one old element. The sum updates in O(1) per step."

Step 3: Explain why you track the sum rather than the average. Say: "I compare sums throughout and only divide by k at the end. Since k is constant, maximizing the sum is the same as maximizing the average. This avoids repeated floating point division and potential precision loss."

Step 4: Be explicit about the initial window setup. Say: "I build the first window sum in a separate loop over indices 0 through k - 1, then initialize maxSum to that value. The sliding loop starts at index k, so the element leaving the window is always nums[i - k], which is valid."

Step 5: Mention the fixed vs. variable window distinction. Say: "This is a fixed-size sliding window because k never changes. In variable-size problems, the window expands or contracts based on a condition. Fixed-size windows are simpler: always one in, one out."

Where This Pattern Appears Next

LeetCode 1343: Number of Sub-arrays of Size K and Average Greater Than or Equal to Threshold uses the same fixed sliding window to maintain a running sum, but the goal is to count windows that satisfy a condition rather than find the maximum. The sliding update is identical.

LeetCode 567: Permutation in String uses a fixed window of size equal to the pattern length and tracks character frequencies inside the window. The window size is fixed, but the condition for a match is more complex. The sliding structure is the same.

LeetCode 239: Sliding Window Maximum uses a variable window in terms of the element tracked (the maximum) but a fixed window in terms of size. It extends today's pattern to require a deque for efficient max tracking, making it a natural difficulty escalation.

LeetCode 209: Minimum Size Subarray Sum flips the window to variable size: find the smallest window whose sum is at least a target. The window shrinks and grows based on the current sum, which is the next level after mastering fixed-size windows.

Key Takeaways

Fixed-size subarrays are the clearest signal for a sliding window. Whenever the problem specifies a contiguous subarray of exactly length k, the sliding window technique almost certainly applies. The window never needs to grow or shrink; it just moves.

Reuse previous computation instead of restarting. The move from O(n × k) to O(n) is not about a new data structure or a clever algorithm. It is about carrying forward a value that was already computed rather than discarding it and starting over. This principle, avoid redundant work by maintaining state, appears across every level of difficulty in DSA.

Compare sums throughout and convert to average only at the end. Dividing inside a loop when the divisor is constant is wasteful and introduces floating point overhead. Deferring division to the final step keeps the inner loop working with integers and the precision constraint becomes trivial.

Fixed and variable windows are different problems. Mastering the fixed-window pattern here, where every step is exactly one in and one out, prepares you for variable-window problems where the expand and contract logic introduces much more nuance. Always identify which type you are dealing with before writing any code.

Closing

Day 10 is complete. A problem that looks like it might require summing every subarray from scratch turns out to need nothing more than one addition and one subtraction per step, once you see that adjacent windows share almost all of their elements.

On Day 11, we continue building the sliding window toolkit. The fixed-window foundation we laid today will make variable-window problems feel like a natural extension rather than a completely new idea.

If the "one in, one out" update clicked for you, or if you want to see how this extends to tracking something more complex than a sum inside the window, drop a comment below. Every question shapes the depth of future posts.

See you on Day 11. 🚀

This post is part of my 250 Days DSA Challenge, solving one problem every day with a focus on intuition, patterns, and interview ready thinking.