Maximum Average Subarray I
easyTime: O(n)Space: O(1)
Signals to notice
contiguous subarraythe same-size window keeps movingmaximum/minimum aggregate
Brute force first
Calculate sum for every subarray of size k. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
The key insight
Slide a window of size k: add the new element, subtract the old one. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.
What must stay true
The window sum is always the sum of exactly k consecutive elements. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.
Easy way to go wrong
Off-by-one when initializing the first window — sum exactly k elements first. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.