Compile Ready
Module 2 · Fixed Window

Maximum Average Subarray I

EasyProblem 1 of 17 7 min read ~12 min to solve LeetCode
Sliding WindowFixed WindowArrayRunning Sum
Asked atAmazonGoogleMicrosoftMetaBloomberg

Problem Statement

Given an integer array nums and an integer k, find a contiguous subarray of length exactly k that has the maximum average value. Return that maximum average value.

Input

An integer array nums and an integer k, the required fixed window length.

Output

A decimal number: the maximum average among all contiguous subarrays of length k.

Constraints

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

Examples

Example 1

Input: 
nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: The best length-4 subarray is **[12,-5,-6,50]** with sum **51**, so the average is **51 / 4 = 12.75**.

Example 2

Input: 
nums = [5], k = 1
Output: 5.00000
Explanation: The only valid window contains **5**, so both the best sum and best average come from that one element.

Example 3

Input: 
nums = [-1,-12,-5,-6], k = 2
Output: -5.50000
Explanation: All averages are negative. The largest comes from **[-5,-6]**, whose average is **-5.5**.

Learning Objectives

  • Recognise an exactly **k** sized contiguous subarray as a fixed-window problem.
  • Replace repeated window re-summing with one running sum that updates in O(1).
  • Track the best sum first, then convert it to an average only once at the end.
  • Handle negative values by initialising the best answer from the first complete window.

Intuition

The pattern signal is strong: the problem asks for a contiguous subarray with length exactly k. That means every candidate window has the same size, and each next window differs from the previous one by only two values: one leaves from the left and one enters from the right.

A tempting approach is to compute the sum of every length-k subarray from scratch. That repeats almost all of the same additions. Fixed window removes the waste: compute the first window once, then slide one step at a time by subtracting the leaving value and adding the entering value.

Common mistakes

  • ×Recomputing every length-**k** sum from scratch, which wastes O(k) work per window.
  • ×Dividing on every slide and comparing floating-point values instead of comparing integer sums.
  • ×Initialising the best sum to **0**, which fails when every possible window has a negative sum.
  • ×Removing the wrong left element after the right pointer advances.

Algorithm Explanation

Window setup

Maintain windowSum, the sum of the current length-k window. Because the window size never changes, maximising the average is the same as maximising the sum. Initialise windowSum with the first k elements and set bestSum to that value.

Window visualization

For nums = [1,12,-5,-6,50,3] and k = 4, the first window is [1,12,-5,-6] with sum 2. Slide right by one position: 1 leaves, 50 enters, and the new window [12,-5,-6,50] has sum 51. Slide again: 12 leaves, 3 enters, and [-5,-6,50,3] has sum 42. The best sum is 51, so the best average is 51 / 4 = 12.75.

Algorithm

  1. Sum the first k elements to form the first complete window.
  2. Store that sum as bestSum.
  3. For each right index from k to the end of the array, add nums[right] to include the entering value.
  4. Subtract nums[right - k] to remove the value that just left the window.
  5. Update bestSum if the current window sum is larger.
  6. Return bestSum / k as a double.

Solutions

Solution: Fixed-size running sum

Use one running sum for the current length-k window. Each slide updates that sum in constant time by adding the new right value and subtracting the old left value.

Step-by-step

  1. Compute the sum of indices 0 through k - 1.
  2. Set bestSum to the first complete window sum so negative arrays are handled correctly.
  3. Starting at index k, slide the window right by adding the entering element and subtracting the element k positions behind it.
  4. Keep the largest window sum seen.
  5. Convert the best sum to a decimal average in the return statement.
Time

O(n)

Space

O(1)

Each element enters the running sum once and leaves it at most once.

Java implementation

Loading…

Dry Run

Sample input

nums = [1,12,-5,-6,50,3], k = 4. Track the fixed window sum as each slide removes one value and adds one value.

stepentering valueleaving valuewindow sumbest sum
initial window [1,12,-5,-6]1, 12, -5, -6none22
right = 45015151
right = 53124251

The largest length-4 window sum is 51, so the maximum average is 51 / 4 = 12.75.

Interview Tips

Say the key reduction out loud: for a fixed k, the denominator never changes, so maximising average is equivalent to maximising sum. This avoids floating-point comparison during the scan. Also call out the all-negative case, because correct initialisation from the first complete window is a common interview check.

Likely follow-ups

  • How would the answer change if the window size could be at most **k** instead of exactly **k**?
  • How would you return the start index of the best window as well as the average?
  • How would you process the same query for many different values of **k**?
  • What if the input arrives as a stream and you need the best length-**k** average seen so far?

Similar Problems

Maximum Sum Subarray of Size K
EasyThe same fixed window without the final division by k.
Contains Duplicate II
EasyMaintains a fixed-size window of the last k indices using a set.
Minimum Size Subarray Sum
MediumA variable-size version where the window shrinks after reaching a target.
Sliding Window Maximum
HardUses a fixed window plus a deque to track the maximum value.

Key Takeaways

  • Exactly **k** elements is the strongest signal for a fixed-size window.
  • Adjacent fixed windows differ by one leaving value and one entering value.
  • Compare sums while scanning, then divide once to produce the average.
  • Initialise from the first real window, not from a neutral value like **0**.
Reusable template: Fixed-size window over an array: build the first k elements, slide by subtracting the leaving element and adding the entering element, and update the best answer after each slide.