Sliding window

Sliding window keeps a contiguous range and updates aggregate state as the range expands or shrinks. Fixed windows have predictable movement; variable windows need an invariant such as at most k distinct characters, sum not exceeding target, or all required characters covered.

Trade-off: compare time, memory, and implementation complexity before committing to a structure or pattern.

On interviews: A good explanation names what is stored in the window, when the left pointer moves, and why every element enters and leaves at most once.

Common pitfalls: Negative numbers can break sum-based shrink rules. Forgetting to decrement frequency maps causes stale state. Nested while loops can still be O(n) when movement is monotonic.

Checklist:

• Define fixed or variable window.
• Maintain aggregate state.
• Move left by invariant.
• Explain O(n) via monotonic movement.