Two pointers: the trick that turns O(n squared) into O(n)

There is a category of array problems that looks, at first glance, like it has no better solution than the one every beginner writes: a loop inside a loop. You scan each element, then scan every element that comes after it, comparing pairs. That is O(n squared) — quadratic time. On an array of a million numbers, quadratic is the difference between a result in a second and a result that would take longer than the history of recorded civilization.

Two pointers is the standard way out. The idea is deceptively simple: maintain two indices, usually called left and right, and move them toward each other (or in tandem) based on how the current state compares to what you want. You visit every element once. The whole thing runs in O(n) — linear time.

The trick is not clever data structures or exotic mathematics. It is one insight about what sorted order actually buys you.

What sorted order buys you

Take any sorted array: [1, 3, 5, 8, 12, 15]. Pick two positions — say index 1 and index 4. Their values are 3 and 12; their sum is 15. Now ask: if you want a larger sum, which way do you move? You move one of the pointers outward toward a larger value. If you want a smaller sum, you move one inward toward a smaller value.

This is the monotonic property — the property that moving in one direction always increases a quantity and moving in the other always decreases it. Sorted order guarantees monotonicity. And monotonicity is what makes it possible to throw away half the remaining search space with a single comparison.

In a brute-force nested loop, when you fix the left element and find that the pair is too small, you move the right element forward. But you also try every right element from left+1 to n-1 before you move left. You are doing redundant work because you already know — from the sorted order — that moving left forward will only make the pair smaller, not larger. The structure of the problem already told you to skip those combinations. Sorted order is information; two pointers is how you spend it.

Two-sum on a sorted array, step by step

The problem: given a sorted array of integers and a target value, find a pair of indices i and j (with i < j) such that arr[i] + arr[j] == target. Return the indices, or (-1, -1) if no such pair exists.

Start left at index 0 and right at index n - 1 — the extreme ends of the array.

Compute arr[left] + arr[right]. Three outcomes are possible:

• The sum equals the target. Done. Return (left, right).
• The sum is less than the target. The current left element is too small. Move left forward by one.
• The sum is greater than the target. The current right element is too large. Move right backward by one.

Repeat until left >= right. If you exit the loop without returning, no pair exists.

That is the entire algorithm. Here is why each step is correct. When the sum is too small, you cannot improve it by moving right leftward — that would only make things smaller. The only option that could produce a larger sum is a larger left element. So you advance left and discard all pairs that used the old arr[left] in a single step. When the sum is too large, the symmetry is exact: you cannot improve it by moving left rightward, so you retreat right and discard everything that used the old arr[right]. Every comparison eliminates an entire column or row of the conceptual pair matrix. The nested loop visits every cell of that matrix; two pointers skips the cells it already knows cannot be the answer.

Why this is not just a trick

Two pointers is sometimes taught as a bag of tricks: “when you see this kind of problem, apply this template.” That framing undersells what is actually happening.

The fundamental idea is search space reduction through structural invariants. An invariant (a property that stays true across every step of the algorithm) is what makes it safe to skip work. In two-sum on a sorted array, the invariant is: “if a valid pair exists, it lies between the current left and right.” Every time you advance left, you can prove that no pair using the old left value remains possible — because the right pointer is already as far right as it can go, and the sum was still too small. Every time you retreat right, you can prove that no pair using the old right value remains possible — because the left pointer is already as far left as it can go, and the sum was still too large.

The invariant holds. The pointer moves are safe. The algorithm terminates in at most n steps.

That chain — sorted structure gives you monotonicity, monotonicity gives you an invariant, the invariant makes bulk elimination safe — is the actual lesson. The two-sum problem is just a vehicle.

Where the pattern generalizes

Once you see the underlying mechanism, a cluster of problems stops looking like a zoo of unrelated tricks and starts looking like the same problem wearing different costumes.

Reverse an array in place. Start left at 0 and right at n-1. Swap them. Advance both. Stop when they cross. The convergence structure is identical; you just act on every step instead of searching.

Remove duplicates from a sorted array. One pointer (write) tracks where the next unique element should go. Another (read) scans forward until it finds something different from what write last wrote. One pass, no extra array.

Container with most water. You have n vertical lines at integer positions; a container is formed by any two lines and holds water up to the shorter one. You want maximum volume. Again: left at 0, right at n-1. The key insight is that the width of the container shrinks as the pointers converge, so you only want to move toward a potentially taller line — always move the pointer at the shorter line inward. The width loss is certain; the height gain is possible. That asymmetry gives you the greedy rule, and the greedy rule is correct because of the monotonic structure.

Sliding window — the in-tandem variant. Sometimes both pointers move in the same direction, with right expanding the window and left contracting it when a constraint is violated. Find the longest substring without repeating characters. Find the minimum-length subarray summing to at least k. The same logic applies: you always know which pointer to move because the structure of the problem tells you how the relevant quantity responds to each move.

The question worth asking every time

When you look at an array problem and your first instinct is a nested loop, stop and ask a single question before writing any code: does the problem have a monotonic structure I can exploit?

Monotonic structure appears most obviously in sorted arrays. But it also appears in problems where the array is not sorted but a quantity derived from the array changes monotonically as a pointer moves — the water-container area as you shrink the width, the character-count window as you expand or contract it.

If the answer is yes — if you can guarantee that moving a pointer in one direction always changes the relevant quantity in a predictable direction — then two pointers is almost certainly the right tool. The sorted order is the signal. The monotonicity is the engine. The O(n) runtime is the payoff.

The one thing that catches people

The classic mistake is not seeing that the precondition needs to be satisfied. Two pointers on the two-sum problem requires a sorted array. If the array is not sorted, you can sort it first — O(n log n) preprocessing — and two pointers still beats the O(n squared) brute force handily. But if you apply the algorithm to an unsorted array without realizing what you are doing, you will get wrong answers and spend an hour wondering why.

The invariant — “the valid pair, if it exists, is between left and right” — holds only because sorted order makes it true. Strip the sorted order and the invariant collapses. The pointer moves are no longer safe to make. This is why understanding the mechanism matters more than memorizing the template: when you know why the algorithm works, you also know when it does not.

The O(n squared) intuition is not wrong, exactly. It is just pointing at the brute-force pair space without noticing that the sorted structure has already done half the work of organizing it. Two pointers is how you spend that organization.