Sliding Window

What it is

Sliding window maintains a contiguous subrange [left, right] of a sequence, growing or shrinking one end at a time, and incrementally updates a running result — instead of recomputing that result from scratch for every possible subrange.

Fixed vs. variable size

• Fixed-size window — slide a window of constant width k across the array; each step removes the element leaving the window and adds the one entering it, O(1) per step.
• Variable-size window — expand right until some condition is violated (e.g. a "no repeated characters" constraint), then shrink left until it's satisfied again, tracking the best window seen.

Why it's O(n)

Both pointers only ever move forward, never backward. Each element is added to the window and removed from it at most once, so total work across the whole scan is O(n) — versus the O(n²) or O(n³) of checking every subrange explicitly.

Recognizing when it applies

Look for problems asking for a "longest/shortest/best contiguous subarray or substring satisfying X" — that phrasing is the strongest signal that a sliding window replaces a brute-force nested loop.