ASAPUtils
The signal
“Subarray of length exactly k” — a fixed window, stated as plainly as it ever gets. This is the warm-up for the pattern; do it before Permutation in String.
Approach ladder
1. Brute force — O(n · k)
Sum each window from scratch. Correct; at n = 10⁵ and k = 10⁴ it’s a billion operations.
2. What is it wasting?
Consecutive windows share k − 1 elements. Re-adding all of them throws away the sum you just
computed.
3. Optimal — slide the sum, O(n)
Compute the first window’s sum, then for each step add the entering element and subtract the leaving one.
double findMaxAverage(vector<int>& a, int k) {
long long sum = 0;
for (int i = 0; i < k; i++) sum += a[i];
long long best = sum;
for (int r = k; r < (int)a.size(); r++) {
sum += a[r] - a[r - k];
best = max(best, sum);
}
return (double)best / k;
}
function findMaxAverage(a, k) {
let sum = 0;
for (let i = 0; i < k; i++) sum += a[i];
let best = sum;
for (let r = k; r < a.length; r++) {
sum += a[r] - a[r - k];
best = Math.max(best, sum);
}
return best / k;
}
Compare sums, divide once
Every window has the same length, so sumA / k > sumB / k exactly when sumA > sumB. Dividing
inside the loop buys nothing and introduces floating-point error into every comparison. Keep
integers throughout, divide at the return. This is a small habit that prevents a whole category of
bugs.
Complexity
- Time O(n) — the initial window plus one pass.
- Space O(1).
Traps
- Initialising
bestto 0. On all-negative input, 0 isn’t achievable and you’d return it. Seed with the first window’s sum. - Starting the slide loop at
k - 1instead ofk. You’d subtract an element that never entered. - Dividing inside the loop. Slower and less precise.
- Overflow in C++.
kup to 10⁵ with values up to 10⁴ exceedsint; uselong long.
Blank re-solve prompt
Return the maximum average of any length-k subarray in one pass. Keep the comparison in integers.