CONCEPT · Pupil
Sliding window
also window · subarray window
Two pointers plus a payload (sum, frequencies, deque of maxima). Expand the right end, shrink the left while illegal.
Intuition
The window is the candidate subarray. Monotonicity of 'legal' lets you only shrink, never expand left.
When to reach for it
- Longest subarray with at most k distinct
- Sum ≤ k on positive arrays
- Minimum window substring
Usual pits
- Negative numbers break sum-window monotonicity
- Updating the payload on shrink but not on expand, or vice versa