Pattern Recognition Drill
Easy Arrays & Strings
The Problem
Given array a and window size k, find the maximum sum of any contiguous k elements.
What approach would you use?
Think about it before scrolling down.
Compute first window sum. Slide: subtract a[i-k], add a[i]. O(n) time, O(1) space.
prefix[i+k] - prefix[i] for each window. Same O(n) but uses O(n) extra space.
Common Trap
Recomputing sum from scratch for each window is O(n*k). The slide trick makes it O(n).