Two pointers and sliding window

Turn O(n²) nested scans into O(n) single passes. Two indices + maintain the window's state incrementally.

Three shapes

• Variable window: grow right, shrink left to keep an invariant
• Two ends: converge from both ends of SORTED data
• Fixed window: add-one, remove-one as it slides (O(1)/step)
• Common trick: update on slide, don't recompute

Watch the window slide

Longest repeat-free substring of 'abcabcbb'. Green = left · orange = right · blue = window. Repeat enters (red) → left JUMPS past it. Answer: 'abc'.

Linear vs quadratic

Length 800: sliding 800 ops, brute 320,000 → 400× less. Drops a whole factor of n.

Why it's O(n) — and when it isn't

• Each pointer only advances → total movement ≤ 2n (amortized, like KMP)
• Needs a MONOTONE window: extending violates, shrinking-left restores
• Breaks on subarray-sum-with-negatives → use prefix-sum hash map
• Two-ends variant needs SORTED input

Takeaway

See a nested loop re-scanning overlapping ranges? Ask: can I maintain it incrementally? The rolling-hash / KMP "reuse what you computed" insight, as a pattern. Next: binary search on the ANSWER, not an array.