Overview
Maintain a window of elements over an array, expanding or shrinking it to meet a constraint.
Analogy
A moving spotlight on a stage: it illuminates a fixed or variable segment that slides across.
Step-by-step
- Fixed window k: sum first k, then slide — subtract left, add right.
- Variable window: expand right until constraint violated, shrink left until valid.
- Track max/min window size that satisfies the constraint.
Visual
[1,2,3,1,4,5], k=3: sum=6 → slide → sum=6 → sum=8 → sum=10
Common mistakes
- Not initializing the window result before sliding.
- Forgetting to shrink the left pointer in variable-window problems.
Practice questions
- Find maximum sum subarray of length k.
- Find smallest subarray with sum ≥ target.
Space
O(1) or O(k) for window storage
AI Wisdom