Given an array and a number k, find the contiguous subarray of length k with the largest average. Return that average.
DSA Animator › DSA Revision › Arrays › Maximum Average Subarray I
Remember: a fixed window slides by adding the new number and removing the oldest. Same length means the largest average is the largest sum. The video solves Maximum Average Subarray I (LeetCode 643, Easy) with the Fixed Sliding Window pattern from the Arrays topic, and you can replay every step in the interactive Maximum Average Subarray I animation.
Given an array and a number k, find the contiguous subarray of length k with the largest average. Return that average.
For 1, 12, minus 5, minus 6, 50, 3, with k equal to 4, the best window is 12, minus 5, minus 6, 50. Its sum is 51, so the average is 12.75.
Summing every window from scratch costs O of n times k. Neighbouring windows share almost all their numbers, so that work is repeated.
Since every window has the same length, the largest average is just the largest sum. Compute the first window once. Then slide: add the number entering on the right, and subtract the one leaving on the left.
The first window, 1, 12, minus 5, minus 6, sums to 2. Slide right: 50 comes in and 1 leaves, so the sum becomes 51, the new best. Slide again: 3 comes in and 12 leaves, so the sum drops to 42. The best sum is 51, and 51 divided by 4 is 12.75.
In code, add up the first k numbers. Then for each new index, add the incoming number and subtract the one k places back. Keep the largest sum, and divide by k at the end. Each number is added and removed once, so it's O of n time and O of 1 space.
Remember: a fixed window slides by adding the new number and removing the oldest. Same length means the largest average is the largest sum.