Two pointers

The idea

Each step rules out one item for good

Looking for two numbers in a list that add up to a target, the obvious approach tries every pair: n(n − 1) ÷ 2 checks, O(n²). If the list is sorted, there is a much better way.

Put one index, L, at the smallest number and another, R, at the largest. Add them. If the sum is too small, the number at L is hopeless: pairing it with anything other than the largest number left gives an even smaller sum. So move L right. If the sum is too big, the number at R is hopeless for the same reason, so move R left. Every step throws one number out, so the search ends within n steps.

The rule

Two pointers works when you can tell, from the two items under the pointers, which one can't be part of any answer. Discard it, move that pointer, and the search is O(n) with O(1) extra space.

Spotting it

Sorted input and pairs are the strongest signals

A sorted list and a pair or triple with a target sum

The sum tells you which end to move

Reverse, or check a palindrome, in place

Ends move toward each other, swapping or comparing

Remove duplicates or zeros in place, keep the order

A read pointer runs ahead; a write pointer marks where kept items go

"Use O(1) extra space" where a hash set would be the easy answer

Pointers replace the memory

Basic

Find a pair with a target sum in a sorted list

The plainest case: one pair, one target, pointers at both ends. Watch how each comparison decides which pointer moves.

Five checks for six numbers. Trying every pair could have taken up to fifteen. The walkthrough counts positions from 0; LeetCode counts from 1, so there the same pair is [3, 4].

Medium

Find every triple that adds up to zero

3Sum adds two things. First an outer loop: fix one number, then run the pair search on the numbers after it, looking for a pair that cancels it. Second, duplicates: the list may hold the same value twice, and the same triple must not be reported twice. Sorting first makes both easy, because equal values end up side by side and can be skipped.

Sorting costs O(n log n) and the pair search runs once per fixed number, O(n) each: O(n²) in all, down from O(n³) for trying every triple.

Hard

Water trapped between bars

Water above a bar rises to the lower of the tallest bar on its left and the tallest on its right. Two pointers find it without storing either: whichever side is currently lower is the one whose wall decides, because the other side is known to have something at least as tall. Count that side's water and move its pointer inward.

The template

The shape to reuse

1L ← 0
2R ← length of xs − 1
3while L < R
4 if the pair at L and R is the answer
5 return it
6 else if the pair is too small
7 L ← L + 1
8 else
9 R ← R − 1

The other common shape keeps both pointers at the front: a read pointer visits every item, and a write pointer only moves when an item is kept. That is how duplicates or zeros are removed in place, in one pass.

Traps

Where two-pointer solutions go wrong

Unsorted input

The "too small, move L" logic is only valid in sorted order. On an unsorted list either sort first (O(n log n)) or use a hash set of numbers seen so far (O(n) time, O(n) memory), which is the usual answer when you need the original positions.

`L ≤ R` instead of `L < R`

A pair needs two different positions; with ≤ the same item can pair with itself.

Duplicate answers

When several equal values sit side by side, skip the repeats, or the same triple appears more than once.

Moving the wrong pointer

Before writing the code, say out loud why the item you discard can't be in any answer. If you can't, two pointers may not apply.

Check yourself

3 questions

1. In a sorted list the pointers show 2 and 9, and the target sum is 8. Which pointer moves?

2. Why does the loop run while L < R and not L ≤ R?

3. To remove duplicates from a sorted list in place, keeping the order, where do the two pointers start?

Takeaways

Remember this

Two pointers discards one item per step, which turns a pair search on a sorted list from O(n²) into O(n).
Pointers at both ends suit sums and palindromes; a read and a write pointer suit in-place filtering.
It needs a reason each discarded item can't be an answer; on unsorted data, sort first or use a hash set.

Practice

Now solve some yourself

Mixed with topics you have practiced 0 unlocked

5 more once you have practiced Greedy algorithms, Prefix sums, Fast & slow pointers, Hash tables & maps. Play one of its examples to the end and solve one of its problems to unlock them.

Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.