Two indices walking an array — converging from the ends or chasing each other — turn a nested-loop pair search into a single linear sweep. The trick is almost always a sorted or symmetric structure that tells you which pointer to move.
A nested loop over an array is really scanning an n × n grid of pairs. If the array is sorted, each comparison tells you an entire row or column can't hold the answer — so you delete it and never look again. Two indices walking inward do exactly that, turning the n² grid into a single O(n) walk.
Hold two pictures in your head, because two pointers comes in two flavors and you pick by asking one question.
fast is a reader that touches every element; slow is a writer (or a trailing chaser) that only advances when something is worth committing.The brute force you're replacing literally inspects every cell of an n × n grid of pairs:
Brute force asks: of ALL pairs, which sums to the target?
j→ 2 7 11 15
i↓ ┌────┬────┬────┬────┐
2 │ │ ✓ │ │ │ n rows × n columns
7 │ │ │ │ │ = n² cells to inspect.
11 │ │ │ │ │
15 │ │ │ │ │
└────┴────┴────┴────┘
Two pointers never visits a cell twice. Each step throws away a
WHOLE row or column — so the n² grid collapses to one n-long walk.On a sorted array, converging pointers throw away a whole row or column per step. Watch L and R squeeze toward the answer:
target = 13 too small → L→ | too big → ←R
[ 2, 4, 6, 9, 11, 15 ]
L→ ←R 2 + 15 = 17 > 13 move R in
[ 2, 4, 6, 9, 11, 15 ]
L→ ←R 2 + 11 = 13 = 13 FOUND ✓
▲ ▲
WHY it never skips: arr is sorted, so arr[R] is the LARGEST partner
left for arr[L]. If even THAT overshoots, every other partner does
too — so L can't be in the answer. Discard it and step L up.
The span [L..R] shrinks by one each step → at most n steps.The fast/slow flavor looks nothing like a grid — it's a write head trailing a read head, compacting in place:
Remove every 0, keep order, O(1) space. s = write, f = read
start [ 1, 0, 2, 0, 0, 3 ] s=0 f scans →
f sees 1 (keep): write@s, s→1
step [ 1, 0, 2, 0, 0, 3 ] f sees 0 (skip): s stays
s
... f sees 2 (keep): write@s, s→2
[ 1, 2, 2, 0, 0, 3 ] f sees 3 (keep): write@s, s→3
s
result [ 1, 2, 3 | _, _, _ ] prefix [0..s) is the answer.
slow advances only when fast finds a keeper, so slow ≤ fast always:
read head leads, write head trails — one pass, nothing overwritten.When a problem smells like pairs, a window, or an in-place edit, climb these rungs in order. The flavor falls out by the third step:
L up only ever increase the measurement, and pushing R down only ever decrease it? If yes → converge from the ends.O(1) space, or detecting a cycle, is fast / slow: a writer that trails a reader (or a tortoise that trails a hare).Each flavor has one sentence that, if true at every step, proves the whole thing correct. Say it before you code:
[L..R].” Every move only discards pairs that are provably not the answer, so the window can shrink without fear.[0..slow) is already finalized and correct, and slow ≤ fastalways.” The writer never passes the reader, so nothing is overwritten before it's read.This is the heart of converging two pointers, and the one thing interviewers probe. Suppose the array is sorted and arr[L] + arr[R] is too small.
arr[R] is the largest partner that exists for arr[L] — every other index between them holds a smaller value. So if even the biggest partner undershoots the target, no partner can reach it. arr[L] is hopeless; discard it forever and step L up. (Symmetrically, too big ⇒ shrink R.)
That's why one comparison eliminates a whole row or column of the pair grid, not a single cell — and why the span [L..R] shrinks by exactly one each step, giving O(n).
Strip away the specific problem and each flavor is a tiny fixed shape. Converging is a three-way branch inside a shrinking while:
# CONVERGING — the array must be sorted (or sort it first)
L = 0; R = n - 1
while L < R:
measure = f(arr[L], arr[R]) # sum, area, palindrome check ...
if measure == target: return hit
if measure too SMALL: L += 1 # only a bigger-left value helps
else: R -= 1 # only a smaller-right helps
# each line of the loop retires one pointer → O(n) totalFast / slow is a single forward for with a guarded write:
# FAST / SLOW — one pass, write head trails the read head
slow = 0 # next slot to overwrite
for fast in 0 .. n-1: # reads EVERY element once
if keep(arr[fast]):
arr[slow] = arr[fast] # commit a keeper
slow += 1
return slow # length of kept prefixThe only things that change per problem are the measurement (sum vs. area vs. char-equality) and the keep predicate. The pointer choreography never changes — which is exactly why two pointers becomes reflexive once you've seen Two Sum II, container-with-most-water, valid palindrome, and remove-duplicates side by side.
lo on the smallest value and hi on the largest. The sum vs. the target tells you exactly which wall to move — and once a wall is moved, it never comes back.Open the Visualize tab and step through it: watch the in-play span between lo and hishrink by one every single step. That's the whole O(n).
You keep two indices into the same array (or two arrays) and move them with intent, never resetting them back. Because each pointer only ever moves forward, the whole array is processed in O(n) total — even though it looks like a double loop.
There are two dominant shapes:
lo starts left, hi starts right, they squeeze inward. Needs a sorted array (or a symmetric quantity like area/palindrome).fast scans ahead while slow marks a boundary. Used for in-place filtering, dedup, and partitioning.arr[lo] + arr[hi] is too small, then no pair using lo can ever reach the target — arr[hi] is already the biggest partner available. So you can discard lo forever and move it up. Symmetric logic shrinks hi.That one observation is what collapses O(n²) into O(n): every comparison permanently eliminates an entire row or column of the pair matrix, not just one cell.
If the array isn't sorted yet, you usually pay O(n log n) to sort first — still a big win, and the sort is what unlocks the technique.
9. First the prerequisite that makes the trick legal: sort. Sorted? Squeeze both ends.Two pointers is the answer when the work is fundamentally about pairs or a window of positions in a linear structure, and either the data is sorted or you can sort it without losing the answer.
| "find a pair / triplet that sums to X" + array | sort, then converge from both ends |
| "the array is sorted" and you want O(1) space | opposite-ends two pointers |
| "remove / dedupe / partition in place" | fast/slow (slow = write boundary) |
| "is it a palindrome?" / compare from both ends | converging pointers |
| "max area / container / most water" | ends inward, move the limiting side |
| "merge two sorted arrays / lists" | one pointer per array |
When → The array is sorted and you want a pair (or to compare ends). Move the pointer that brings the comparison closer to the target.
function squeeze(arr: number[], target: number): [number, number] | null {
let lo = 0, hi = arr.length - 1; // start at both ends
while (lo < hi) {
const sum = arr[lo] + arr[hi];
if (sum === target) return [lo, hi];
if (sum < target) lo++; // too small → grow the left value
else hi--; // too big → shrink the right value
}
return null;
}lo < hi → stops the two pointers from crossing or landing on the same index (which would reuse one element).When → In-place filtering, dedup, or partition. slow marks where the next kept element goes; fast scans every element.
function partition(arr: number[]): number {
let slow = 0; // boundary of the "kept" region
for (let fast = 0; fast < arr.length; fast++) {
if (keep(arr[fast])) { // some predicate
[arr[slow], arr[fast]] = [arr[fast], arr[slow]];
slow++;
}
}
return slow; // length of the kept prefix
}When → k-sum style problems (3Sum, 4Sum). Sort, fix an outer anchor, then run opposite-ends on the remaining suffix. Skip duplicate anchors and duplicate landings to keep results unique.
function triples(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const out: number[][] = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue; // skip dup anchor
let lo = i + 1, hi = nums.length - 1;
while (lo < hi) {
const sum = nums[i] + nums[lo] + nums[hi];
if (sum === 0) {
out.push([nums[i], nums[lo], nums[hi]]);
while (lo < hi && nums[lo] === nums[lo + 1]) lo++; // skip dups
while (lo < hi && nums[hi] === nums[hi - 1]) hi--;
lo++; hi--;
} else if (sum < 0) lo++;
else hi--;
}
}
return out;
}lo/hi values before stepping both inward.Converging pointers rely on order. If the input isn't guaranteed sorted, sort it (or confirm the problem hands you sorted data). On an unsorted array the "move the smaller side" logic is meaningless.
Use lo < hi when the two pointers must stay distinct (pairs), and lo <= hi only when a single middle element is itself valid. Mixing these double-counts or skips the center.
The most common 3Sum bug: emitting [−1,−1,2] twice. After recording a triplet, advance past all equal values on both sides before moving on, and skip a repeated outer anchor entirely.