Two Pointer & Sliding Window

One of the most disarming wins in algorithms is watching an "obviously O(n²)" problem collapse into a single linear pass. You keep two indices, move them carefully, and every pair (i, j) that could matter gets considered — without ever writing a nested loop. That's the entire pattern.

The two families

Two-pointer problems come in two shapes, and mixing them up is the first mistake to avoid.

Converging pointers on sorted data. Two indices start at opposite ends and squeeze toward the middle. Each step, you inspect arr[left] and arr[right], decide which pointer to move, and shrink the search space by one. Works when the data is sorted (or otherwise ordered in a way that makes "moving one pointer" monotone). Classic examples: pair-sum on a sorted array, container-with-most-water, three-sum (which wraps a two-pointer inside an outer loop).

Sliding window on a linear scan. Both pointers start at 0 and walk right. right always advances; left advances only when some invariant about the window [left, right] has been violated. The window tracks "the best run ending at right" and the global best is the max we've ever seen. Classic examples: longest substring without repeating characters, minimum window substring, maximum sum of a length-k subarray.

Why the brute force collapses

The obvious algorithm for "find the longest distinct-char substring in s" is to consider every pair (i, j) with i ≤ j, check whether s[i..j] is distinct, and keep the longest. That's O(n²) substrings, each taking O(n) to scan — total O(n³). A little cleverness with a set drops it to O(n²). A sliding window drops it to O(n).

The key insight: once right has moved past some character c, you never need to consider a window that started before the last occurrence of c — it would already contain a duplicate by the time right is here. So left only ever moves right. Since both pointers move monotonically and each can only move n times, the total work is O(n). The inner while (seen.has(incoming)) left++ loop looks like a nested loop, but amortised over the whole run it fires at most n times total.

Canonical problems

Problem	Pattern	Invariant
Longest substring without repeats	Sliding window	Window is a set of distinct chars
Pair sum (sorted)	Converging	Left + right sum relative to target
Container with most water	Converging	Current pair is the widest worth considering
Minimum window substring	Sliding window	Window contains all required chars
Max sum of length-k subarray	Fixed sliding window	Window width = k
Three sum	Outer loop + converging	Outer anchor, inner two-pointer on suffix

If you find yourself writing for i ... for j > i and the inner loop decision is monotone in some quantity — "too big / too small / just right" — the two-pointer pattern will usually apply.

When the pattern applies

The two-pointer pattern is a linear scan in disguise. It applies when:

1. The input is sorted or the decision to move a pointer is monotone. For converging pointers, this means the array is ordered so that "bumping left raises the sum" and "dropping right lowers the sum" are both facts the algorithm can rely on. For sliding windows, it means the condition that triggers left-advancement is a property of the window interior that doesn't improve by keeping a duplicate in scope.

2. The answer is a contiguous range. Two pointers describe a range [left, right] — so the pattern is ideal when the answer is "the best substring" or "the best subarray." It's not ideal for problems where the best candidate is a scattered subset (those want hashing or DP).

3. Linear work per step is enough. If checking the window state is itself O(n), the outer pattern isn't buying you much. Usually there's a running aggregate (a set, a sum, a counter) that updates in O(1) as one end advances and the other retreats.

Gotchas

Off-by-one on window boundaries. The window can be inclusive on both ends [left, right] or half-open [left, right). Pick one convention and stick to it for the whole function. Mixing means you'll either double-count or miss the last element. Most implementations use inclusive/inclusive with right driving the outer loop.

Which direction to shrink. For converging pointers, the sign of the error tells you: sum < target → bump left; sum > target → drop right. For sliding windows, the trigger for shrinking is violation of the window invariant, not "the window got big enough." Shrinking because the window reached some length is how you end up accidentally solving a "fixed window" problem as a "variable window" one.

Duplicate handling. The longest-substring tracer in this level uses Set membership to detect "incoming char is in the window." A faster variant maps each char to its last seen index — on a repeat, you can jump left straight to lastIndex + 1 rather than stepping. Both are O(n) amortised; the jumping version has a better constant factor but an extra edge case (ignore last-index matches that fell out of the window naturally).

Don't shrink past the answer. When you find a valid window, record it before continuing to shrink. Forget, and you'll report the shortest valid window when the problem asked for the longest (or vice versa).

Playground

Pick a problem family from the dropdown: the sliding-window "longest substring" or the converging "pair sum on sorted array." Type your own input; the frame counter walks through every pointer move. Each cell is labelled with its index; L and R sit under the current pointer positions; the window between them is highlighted; the running "best" sits at the bottom.

Step through abcabcbb manually — watch the window grow to abc (length 3), shrink by one when the second a arrives, then re-grow. That shrink event is the entire trick.

Visualizer

The Window Animator loops a pre-recorded trace of abcabcbb. The pointer bars slide using CSS transitions so the motion reads as continuous, not frame-by-frame — that continuity is the picture you want in your head when writing the algorithm. The best-so-far underline ticks up exactly when the window would.

The eye is meant to catch one thing: both pointers only ever move right. That's what "linear" means.