Pattern 2: Two Pointers

Two indices that move intelligently. The secret of the pattern isn't the pointers — it's the argument that lets you discard candidates in bulk without even looking at them.

Did you try? The brute force tests all pairs of walls — O(n²) — and works on the small examples, but it would be too slow for large inputs. The annoyance: many of those pairs obviously can't be the answer. The theory below shows how to discard them in bulk.

The theory: what problem does two pointers solve?

Many problems ask for the best pair (or triple) of elements: the pair that sums to the target, the pair that forms the largest container, the triple that sums to zero. The brute force tests all pairs: O(n²).

Two pointers attacks the central waste of that brute force: it tests pairs that have no chance of being the answer. If the array has some structure — it's sorted, or the quality of the pair depends on the shorter side — you can prove that whole blocks of pairs are useless and skip them all at once.

The classic mechanics (converging pointers)

left  = start of the array
right = end of the array
while left < right:
    evaluate the pair (left, right)
    decide WHICH pointer to move — and the move discards
    all the pairs that involved the abandoned position

Each step eliminates a whole position (and all the pairs with it). There are n positions, so the loop runs at most n times: O(n). The magic is in the decision of which pointer to move — and it requires a justification.

The perfect example: pair that sums to the target, in a SORTED array

Sorted array, I look for two numbers that add up to target:

• If nums[left] + nums[right] is less than the target → the sum needs to grow. Moving right to the left only decreases the sum. So the only useful move is left += 1. And more: we just proved that nums[left] doesn't pair with anyone (even the largest element was too small) — we discard n pairs at once.
• If the sum is greater → symmetric: right -= 1.

This is the heart of the pattern: each move comes with a proof of discard. Without the proof, two pointers is guesswork.

The signals in the statement

• The array is sorted (or sorting doesn't ruin the answer).
• The question involves pairs/triples with some condition on sum, distance or size.
• You can reason: "if the current pair fails by excess, moving pointer X doesn't help".
• They ask for O(1) space (a hash map would spend O(n)).

Example 1 — Container With Most Water

"Each position is a wall of height heights[i]. Choose two walls that form the container holding the most water." The water is limited by the shorter wall: area = (right - left) × min(height_left, height_right).

• Brute force: all combinations of walls — O(n²).
• The waste: if the left wall is the shorter one, any other pair with it and a closer wall is worse: the width shrinks and the height stays locked by the same shorter wall. All those pairs are useless.
• The pattern: start with the widest container (the ends) and, at each step, abandon the shorter wall — it's the only hope of finding something better.

Watch the decision rule at work (notice: the pointer that moves is always the one at the shorter bar):

Why is it O(n)?

On each pass of the loop, left goes up or right goes down — the pointers only move one toward the other and never go back. They cross after at most n-1 moves, and each pass does only O(1) work (comparisons and arithmetic). Total: O(n) time, O(1) space — this pattern doesn't even ask for extra memory.

Example 2 — 3Sum (the composite pattern)

"Find all triples that sum to zero, without repeating triples." It looks like another universe, but it's the "pair that sums to the target" problem used as a building block:

1. Sort the array — O(n log n). (Now two pointers becomes available!)
2. Fix the first number nums[i] — a loop O(n).
3. The rest became: "in the sorted slice to the right of i, find pairs that sum to -nums[i]" — exactly the theory's example, O(n) with two pointers.
4. Skip repeated values as you advance (so you don't duplicate triples).

Why is it O(n²)?

Outer loop O(n) × pointer sweep O(n) = O(n²); the sort O(n log n) is smaller and disappears in the sum (rule 1 of the fundamentals). For a problem whose brute force is O(n³), O(n²) with O(1) space is the state of the art.

Hash map or two pointers? (both solve pairs!)

Summary

• Two pointers = proven discard of candidates in bulk; the proof for each move is mandatory.
• Converging: O(n) because the progress is irreversible — each step consumes a position.
• Costs O(1) space — an advantage over the hash map when the array is sorted or the condition is an inequality.
• Triple problems = fix one + two pointers on the rest (3Sum, O(n²)).

Next lesson: when the question is about contiguous slices of the array — sliding window.