easy

Maximum Average Subarray I

Find the contiguous subarray of a fixed length with the largest average.

1. Define the problem

Maximum Average Subarray I

You are given an integer array nums 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. Answers within 10-5 of the actual answer are accepted. Use a fixed length window of length k and slide it while tracking the running sum.

Constraints

  • n == nums.length
  • 1 ≤ k ≤ n ≤ 105
  • -104 ≤ numsi ≤ 104

Example

Inputnums = [1, 12, -5, -6, 50, 3], k = 4
Output12.75

Explanation The subarray [12, -5, -6, 50] has sum 51, so the average is 51 / 4 = 12.75.

2. Know the words first

In plain terms

Contiguous subarray
A run of elements sitting right next to each other in the array, with nothing skipped — not just any subset you could pick.
3. Visualize the solution

Slide a fixed window of size 4

Slide a fixed window of size 4
Statusinit

Window [1, 12, -5, -6]: sum = 2, avg = 0.50 — best so far.

What happens in this step

window = [0, 3]  (size 4)

sum = 1 + 12 + (-5) + (-6) = 2
avg = 2 / 4 = 0.50

This is the first window, so it starts out as the best average seen so far.
Step 1 of 3

Steps to visualize

  1. Place a window of length k on the first k elements and compute its sum.
  2. Record that average as the best so far.
  3. Slide one step right: drop the leftmost value, add the new rightmost value.
  4. Update the best average whenever the window sum improves.
  5. Stop when the window reaches the end of the array.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Slide a fixed window of size 4
Statusinit

Window [1, 12, -5, -6]: sum = 2, avg = 0.50 — best so far.

What happens in this step

window = [0, 3]  (size 4)

sum = 1 + 12 + (-5) + (-6) = 2
avg = 2 / 4 = 0.50

This is the first window, so it starts out as the best average seen so far.
Step 1 of 3
5. Solution

Solution

solution.tsTypeScript
function findMaxAverage(nums, k) {
  if (k <= 0 || k > nums.length) {
    throw new Error("k must be between 1 and nums.length");
  }

  let windowSum = 0;
  for (let i = 0; i < k; i++) {
    windowSum += nums[i];
  }

  let maxSum = windowSum;

  for (let right = k; right < nums.length; right++) {
    const left = right - k;
    windowSum += nums[right] - nums[left];
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum / k;
}
Time
O(n)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
nums = [1, 12, -5, -6, 50, 3], k = 412.75example from the docstring
nums = [5], k = 15smallest valid input: k === nums.length
nums = [4, 2, 9, 1], k = 19k === 1 just picks the max element
nums = [0, 0, 0, 0, 10, 10, 0], k = 210window must slide across the whole array to find the best average
nums = [3, 3, 3, 3], k = 23all identical elements
nums = [-5, -1, -8, -2], k = 2-3handles negative numbers
nums = [1, 4, 2, 10, 23, 3, 1, 0], k = 312larger, hand-verified case
nums = [1, 2], k = 5throwsthrows when k is larger than the array

Keep reading