Two pointers
AlgorithmsHigh priority~1 hTwo indices scanning a sequence to collapse an O(n²) nested loop into a single O(n) pass.
Definition
The two-pointer pattern walks a sequence with two indices instead of nesting two loops. The common shape is opposite ends — left at the start, right at the end, moving toward each other — but fast/slow (same direction, different speeds) is the same idea. Each pointer advances at most n times, so the whole scan is O(n) with O(1) extra space.
When to use
Reach for two pointers on a sorted array or string when you'd otherwise compare all pairs: finding a pair that sums to a target, checking a palindrome, partitioning in place, or removing duplicates. The key is that moving a pointer must let you discard possibilities monotonically — otherwise you'd still need the nested loop.
Techniques
Inward (opposite ends) — left at the start, right at the end, converging; move whichever side can't improve the answer where it is (pair sum on a sorted array, palindrome check, container with most water).
Unidirectional (fast/slow) — both start at the same end and move the same way at different speeds or roles; one scans ahead while the other marks a boundary (in-place dedupe, cycle detection).
Staged — one pointer searches for a trigger element, then a second sweeps from there to gather what follows.
Related structures
Relation to sliding window
A sliding window is a directional two-pointer variant: both pointers move the same way and the span between them is the answer. If the two pointers instead converge from opposite ends, it's the classic two-pointer scan. See the sliding window topic.
Implementation
let left = 0;
let right = arr.length - 1;
while (left < right) {
// inspect arr[left] and arr[right]...
// ...then advance the side that can only get better by moving:
if (shouldMoveLeft) left++;
else right--;
}Worked examples
Container With Most Water — pick two lines that, with the x-axis, hold the most water. Start at the widest pair (both ends). The area is capped by the shorter wall, so moving the taller one in can only shrink the width without lifting the cap — move the shorter wall instead, hoping for a taller one.
height = [1, 8, 6, 2, 5, 7]
Widest pair, but the left wall (1) caps the area — move it in.
best = 28. Now the right wall (7) is the shorter one, so move right.
Narrower and a lower cap — 15 can't beat 28.
Still shrinking; the right wall keeps capping us.
No remaining pair can beat 28. Answer: 28.
function maxArea(height) {
let left = 0;
let right = height.length - 1;
let best = 0;
while (left < right) {
const area = Math.min(height[left], height[right]) * (right - left);
best = Math.max(best, area);
// the shorter wall caps the area, so move it inward
if (height[left] < height[right]) left++;
else right--;
}
return best;
}left and right each move inward at most n times before they meet, so the whole scan is O(n) time and O(1) space — versus the O(n²) of checking every pair.
Things to look out for
- Two pointers needs a monotonic reason to move — on an unsorted array, advancing a pointer doesn't safely discard candidates. Sort first, or reach for a different tool.
- Decide up front whether the loop is
while (left < right)or<=— the crossing condition is the usual off-by-one. - When mutating in place, keep a clear write pointer separate from the read pointer.
Corner cases
- Empty or single-element input.
- All-duplicate values (in-place dedupe collapses to length 1).
- Already-sorted vs. reverse-sorted inputs.
- No valid pair — return the prompt's sentinel (e.g.
[]or-1).