Two Pointers

Two pointers is the technique you reach for when a brute-force solution says “for every element, look at every other element” — and you can see that most of those pairs are never worth looking at.

Why it works#

The brute force is two nested loops: O(n²) work, because it re-examines pairs it has already ruled out. Two pointers gets the same answer in one pass by holding a single statement true from beginning to end:

Each pointer only ever moves in one direction, and every step permanently eliminates candidates that can no longer be the answer.

A statement like that has a name. An invariant is something you arrange to be true before a loop starts, keep true through every single iteration, and therefore know is still true once the loop ends. It is the difference between believing your code works because the examples passed, and knowing it works because nothing the loop does can break the promise. When a solution has an off-by-one bug, it is almost always because some step quietly violated an invariant nobody had written down.

That invariant is what makes two pointers correct, and it is also what makes it fast. If each pointer moves at most n times and never backtracks, the whole scan is O(n) no matter how the two interleave. The interesting question in any two-pointer problem is never “where do the pointers go” — it is “what does moving this pointer rule out, and how do I know?” Get that argument right and the code follows.

Three arrangements cover almost everything you will meet.

Opposite directions#

Two pointers start at the ends and walk toward each other. This needs sorted input — or some other ordering that lets you compare against a target — because the argument depends on knowing which direction makes a value bigger or smaller.

The classic case: find two values that sum to a target.

Follow the reasoning at each step. When the sum is too big, the right value is the problem: it is the largest one still available, so every pair that uses it is at least this large. Nothing to the left can rescue it, so it is discarded forever and R moves in. When the sum is too small, the mirror argument discards the left value.

lo = 0
hi = n - 1

while lo < hi:
    sum = a[lo] + a[hi]

    if sum == target:
        return (lo, hi)
    else if sum > target:
        hi = hi - 1      // a[hi] is too large for any remaining partner
    else:
        lo = lo + 1      // a[lo] is too small for any remaining partner

return none              // pointers met, nothing left to check

The loop ends when lo == hi, because a pair needs two distinct positions. Each iteration throws away exactly one candidate, so the whole search is O(n) after the O(n log n) sort — and free if the input was already sorted.

Same direction#

Both pointers move forward, at different speeds or for different reasons. The one behind usually marks a boundary; the one ahead does the scanning.

The most useful version is read and write: rewriting an array in place, where write marks the end of the finished prefix and read looks for the next element that belongs there.

Notice that write only advances when something is actually kept. That is the invariant: everything before write is final and correct, which is why the answer is simply the prefix once read falls off the end.

write = 0

for read = 0 .. n - 1:
    if keep(a[read]):
        a[write] = a[read]
        write = write + 1

// a[0 .. write - 1] is the answer

The other common pairing is fast and slow, where one pointer moves two steps for every one of the other’s. Because they close the gap at a constant rate, the fast pointer reaches the end in half the steps — which is how you find a midpoint in one pass, and how you detect a cycle without any extra memory: in a loop the fast pointer eventually laps the slow one, so the two must meet.

Sliding window#

Both pointers move forward again, but now they bound a contiguous range, and you maintain a running answer for whatever is inside it. The right edge extends the window; the left edge shrinks it whenever the window stops being valid.

The shape is always the same: grow greedily, shrink only when you must. What changes between problems is the definition of valid — no repeated characters here, but it could be a sum under a limit, or at most k distinct values.

lo = 0
best = 0

for hi = 0 .. n - 1:
    add a[hi] to the window

    while window is invalid:
        remove a[lo] from the window
        lo = lo + 1

    best = max(best, hi - lo + 1)

return best

That inner while looks like it makes the whole thing quadratic. It does not: lo never moves backwards, so across the entire run it advances at most n times in total. Both pointers together do at most 2n moves — still O(n).

This form has enough variants — shrinking while invalid versus while valid, fixed-size windows, and the choice of what state to carry — that it gets its own page: sliding window.

Recognising it#

Reach for two pointers when a problem has this shape:

• You are asked about pairs, triples, or contiguous ranges in a sequence, and the obvious solution is a nested loop.
• The data is sorted, or sorting it does not destroy what you were asked for. Sorting is often the missing first step for the opposite-directions form.
• The answer is a subarray or substring, and extending it or shrinking it changes the answer predictably — that is a sliding window.
• You need O(1) extra space, or an in-place rewrite. Read-and-write pointers are usually the intended solution.

And the check that saves you: before writing the loop, say out loud what moving each pointer eliminates. If you cannot justify it, the pointer is moving on a hunch, and the solution will fail on some input you have not thought of yet.

Summary#

One technique, one guarantee: pointers that never turn around, each move retiring candidates that cannot be the answer. Opposite directions narrows a search from both ends. Same direction separates scanning from writing. A sliding window keeps a running answer over a range that only ever slides forward. Once you can state what a move rules out, the boundary conditions stop being guesswork.