The two-pointer pattern family

“Two pointers” is the most overloaded name in interview prep: three genuinely different techniques share it, with different preconditions, different invariants, and different problem tells. Candidates who know one family member and reach for it on the others produce confidently wrong solutions. This page separates the three, because the separation is the skill.

Family one: converging ends

Two indices at opposite ends of a sorted array, walking toward each other; each comparison retires one element permanently, having proven it useless against its best possible partner. This is the family with the full essay and visualization: two-sum on sorted input, 3Sum’s inner loop, container-with-most-water, palindrome checking.

Its tells: pairs, symmetry, or “from both ends”; sorted input given or cheap to create; a comparison that can condemn an extreme forever. Its precondition is absolute — the elimination proof leans on the ends being extremes, so unsorted input silently voids it. Its budget: O(n) time, O(1) space, at most n−1 steps because every step shrinks the window by exactly one.

Family two: slow and fast walkers

Two indices moving the same direction at different speeds — no sortedness required, because nothing is being eliminated-by-comparison; the pointers’ relative positions encode the answer.

The dedup form: slow marks the end of the kept prefix, fast scans everything; each keeper gets copied to slow++. In-place array compaction (“remove duplicates from sorted array”, “move zeroes”) is exactly this, and the invariant is “everything up to slow is the finished output”.

The cycle form — Floyd’s tortoise and hare — is the famous one: walk a linked list with one pointer moving one step and another moving two. In a cycle, the hare laps the tortoise; the gap shrinks by one per step, so they must meet — no visited set, O(1) memory, and a second phase (reset one pointer to the head, walk both at speed one) finds the cycle’s entrance, a fact that feels like magic until you write the modular arithmetic once. Linked-list middles (fast reaches the end when slow is halfway) come from the same speed trick.

Tells: linked lists, “constant space” demands, cycles, “middle of”, in-place compaction. Note what’s absent: no sortedness, no elimination — this family shares nothing with family one except the count of index variables.

Family three: the sliding window

Two same-direction indices bounding a live segment — grow the right end to include more, shrink the left end to restore validity, and harvest an answer at each valid state. “Longest substring without repeating characters”, “smallest subarray with sum ≥ k”, “at most k distinct characters” — the window family owns a large province of string and subarray problems.

Its engine is an invariant on the window’s contents — “no repeats inside”, “sum below the limit” — maintained incrementally: each character entering updates a count; each leaving rolls it back. The linearity argument is the elegant part: both endpoints only ever move forward, so across the whole run each pointer moves at most n times — O(n) total, even though the inner shrink-loop looks nested. That amortized reading (charge each iteration to a pointer movement, of which there are ≤ 2n) is the pattern’s signature interview moment, because the code looks quadratic and isn’t.

Its boundary: windows work when validity is monotone — growing a window can only break the invariant, shrinking can only restore it. “Sum ≥ k with negative numbers allowed” breaks monotonicity (shrinking might raise the sum), and the window silently fails there; prefix sums or other machinery takes over. Knowing the monotonicity boundary is knowing the family.

Choosing under pressure

Ask two questions. Do the pointers move toward each other, or the same way? Toward: family one, and sortedness is mandatory — check it’s given or buy it. Same way: is there a segment whose contents matter (family three — what’s the window invariant?) or just two positions whose relationship matters (family two — speeds or prefix/scan roles)? What does one step prove? An elimination (“this element can never work”) is family one; an invariant maintenance (“the window is valid again”) is family three; pure motion arithmetic is family two.

And the meta-answer worth saying in the room: these are all linear-scan-with-state techniques — the state is just small enough to live in two integers and a counter or two. When someone asks “can you avoid the hash map / extra array?”, the two-pointer families are usually what they’re fishing for, and naming which family, with its precondition, is the difference between pattern-matching and understanding.