#643 Maximum Average Subarray I
the problem
In plain words
Find the contiguous subarray of length exactly k with the largest average, and return that average.
in nums = [1,12,-5,-6,50,3], k = 4
out 12.75
(12 − 5 − 6 + 50) / 4 = 51 / 4 = 12.75.
in nums = [5], k = 1
out 5.0
- 1 ≤ k ≤ n ≤ 10⁵
- -10⁴ ≤ nums[i] ≤ 10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternSliding window (fixed size)
k is fixed, so the largest average is just the largest sum divided by k. Neighbouring windows share k − 1 numbers — update the sum instead of recomputing it.
solutions
From brute force to optimal
For each start, add up the k numbers.
- For start in 0..n−k: sum nums[start..start+k−1].
- Keep the largest sum; divide by k at the end.
n − k + 1 windows, k additions each.
A sum and a best value.
class Solution { public double findMaxAverage(int[] nums, int k) { long best = Long.MIN_VALUE; for (int start = 0; start + k <= nums.length; start++) { long sum = 0; for (int i = start; i < start + k; i++) sum += nums[i]; // re-add all k numbers best = Math.max(best, sum); } return (double) best / k; }}Build the first window, then add the new number and subtract the one leaving.
- sum = first k numbers; best = sum.
- For right = k..n−1: sum += nums[right] − nums[right − k].
- best = max(best, sum). Return best / k.
Each number is added once and subtracted once.
Two integers.
class Solution { public double findMaxAverage(int[] nums, int k) { int sum = 0; for (int i = 0; i < k; i++) sum += nums[i]; int best = sum; for (int right = k; right < nums.length; right++) { sum += nums[right] - nums[right - k]; best = Math.max(best, sum); } return (double) best / k; }}Dry run
in the room
How to say it in the interview
talk track
- Point out that comparing sums is the same as comparing averages because k is fixed — divide once at the end.
- Mention overflow: max |sum| is 10⁵ × 10⁴ = 10⁹, which fits in an int (limit ≈ 2.1·10⁹). Use long if the bounds were larger.
traps
- Dividing with integers: cast first,
(double) best / k. - Starting
bestat 0 — all-negative inputs would return 0 incorrectly.
what they ask next
Follow-ups
Maximum Average Subarray II (LC 644): length at least k?
Binary search on the answer: for a guess x, subtract x from every number and check whether some subarray of length ≥ k has sum ≥ 0 using prefix sums.
before you submit
Edge cases to test
- All numbers negative: start
bestat the first window's sum, never at 0. - k = n: the only window is the whole array.
- k = 1: the answer is simply the largest number.
- Integer division:
best / kon ints drops the fraction — cast first.
practise next
Similar problems
- #209Minimum Size Subarray SumMediumin Sliding Window
- #303Range Sum Query - ImmutableEasyin Hashing
- #239Sliding Window MaximumHardin Queues