Two Pointers

The first time the Two Pointers trick really landed for me, I was watching a candidate brute-force "find two numbers that add up to the target": two nested loops, O(n^2), and the interviewer doing that patient nod while waiting for them to notice the array was already sorted. Sorted is the tell. When the input is ordered and you are hunting for a pair that satisfies some relationship, you almost never need the nested loop.

The move is simple: one finger at each end of the array, and you let the ordering decide which finger to advance.

On the sorted array 1 3 4 6 8 9 with target 10, a left pointer starts at the smallest value and a right pointer at the largest; their sum decides the move, too small advances the left pointer, too large retreats the right, and an exact match records the pair before both step inward, so every element is visited once.

Why walking inward is enough

Take a sorted ascending array and look for two values that sum to target. Put left at the first index, right at the last, and read arr[left] + arr[right]:

  • Too small? The only way to grow the sum is to move left toward larger values. Moving right could only shrink it.
  • Too large? Symmetrically, pull right inward.
  • Exactly right? Record the pair and step both inward.

The insight worth burning into memory: every comparison lets you discard a candidate for good. When the sum comes up short, no pair built on the current left can ever reach the target, because right is already the biggest partner available. So you retire left and never look back. That is why one pass is enough, each step throwing away a whole row or column of the pair grid that brute force would have checked cell by cell.

A quick trace on the toy case [1, 3, 4, 6, 8, 9], target = 10:

leftrightsumaction
1910match, record (1, 9), both move in
3811too big, pull right in
369too small, push left in
4610match, record (4, 6), both move in

The pointers cross and we stop, each element touched at most once. The whole walk is a single loop:

def pair_sums(arr, target):
    left, right = 0, len(arr) - 1
    pairs = []
    while left < right:
        total = arr[left] + arr[right]
        if total == target:
            pairs.append((arr[left], arr[right]))
            left, right = left + 1, right - 1
        elif total < target:
            left += 1
        else:
            right -= 1
    return pairs

O(n) time, O(1) space.

In the wild: intersecting two sorted lists

That toy makes the mechanics clear, but the pattern earns its keep on real data. Search engines lean on it constantly. An inverted index maps each word to a sorted list of the document IDs that contain it, and to answer a query for cat AND dog you need the documents present in both lists: a set intersection over two sorted sequences. The same two-pointer walk does it in a single pass over each list:

def intersect_sorted(a, b):
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            out.append(a[i])
            i, j = i + 1, j + 1
        elif a[i] < b[j]:
            i += 1          # a[i] is too small to ever match, retire it
        else:
            j += 1
    return out

It is the same shape as the pair-sum, only with a cursor per list instead of two ends of one array. At every step the comparison tells you, without ambiguity, which pointer to advance, and each advance permanently discards a value that can never match again. That sameness is the whole point, and the payoff is concrete: intersecting lists of length m and n this way is O(m + n), against the O(m * n) of checking every pair. It is exactly why search engines keep their posting lists sorted, and the same merge is the heart of a merge-join in a database.

Intersection and pair-sum are the same converging walk: at every step one comparison retires a value for good. Reading that in a table is one thing; watching the eliminations happen and scrubbing them back and forth is another, and the DSA Lab lets you do exactly that with the very array traced above:

$ ./dsa-lab --embed
DSA Lab

Interactive playground for algorithm patterns: two pointers and sliding windows on a scrubbable timeline, binary search and search-on-the-answer, sorting comparison (6 algorithms), trees (BST, AVL, Heap, Trie), graph algorithms (Cycle Detection, MST, SCC, Max Flow) and hash collision strategies. Every configuration is deep-linkable.

# The exact array and target from the trace above, now scrubbable. The dimmed cells are pairs proven impossible without ever testing them: drag the timeline backwards if a move surprises you.

The trigger

Sorted or otherwise monotonic data, and you want a pair, a boundary, or a partition. If your instinct on a sorted array is a nested loop, that is the smell: Two Pointers usually collapses it to a single pass.

The word doing the work is unambiguous. The pattern only holds when the current comparison tells you, with no doubt, which pointer to move. Lose that certainty and it falls apart, which is exactly why it craves sorted input.

Problems where it hides

  • Pair with a target sum or difference in a sorted array. The canonical case above.
  • Palindrome check. Same skeleton, you compare the two ends instead of adding them.
  • Remove duplicates or partition in place. A slow pointer marks the end of the "keep" region while a fast pointer scans ahead. This is the quiet workhorse behind Dutch-flag partitioning and quicksort's partition step.
  • Merge or intersect two sorted lists. One cursor per list, advance whichever is behind. It is the merge hiding inside merge sort.
  • Container with most water, closest pair to a target. Move the end that is currently limiting you.

Five disguises, one shape: a boundary you can always move in one clear direction.

Where it bites

The bugs are almost never in the logic between the pointers. They live in the edges. while left < right versus left <= right decides whether you ever inspect the middle element. Advancing one pointer versus both on a match decides whether you double-count or skip. And with duplicates, if you forget to slide past equal values after a hit, you will happily report the same pair twice. When a Two Pointers solution misbehaves, look at the stopping condition first, every single time.

When it is the wrong tool

Two Pointers buys its speed with assumptions, and a pattern is only as good as its fit, so do not force it. Reach for a neighbor instead when:

  • The data is not sorted and sorting would cost more than a hashmap's O(n) scan. Use Hashmaps and Frequency Counting.
  • You need a contiguous range, not a pair. That is Sliding Window, which is really Two Pointers carrying an invariant.
  • You keep testing the same range sums. Precompute a Prefix Sum.
  • The array is sorted and you want one partner at a time. A Binary Search often matches the complexity with less bookkeeping.

References