Two pointers

What & when

Two indices walking a linear structure under a discard rule, collapsing an O(n²) pair search into a single O(n) sweep. Reach for it when the input is sorted (or cheaply sortable) and the question is a pair / triple / sum to a target, when you compare the two ends of an array or string (palindrome, “most water”, reverse-in-place), when filtering in place with a slow write pointer trailing a fast read pointer, or for cycle / midpoint questions on a linked list (the fast/slow variant). Transformation: sorted order lets one comparison discard a candidate permanently. Complexity lever: every step retires at least one index, so the O(n²) pairs collapse to O(n). Part of the DSA patterns hub.

Skeleton

The flagship opposing-pointers template (same-direction and fast/slow reuse the same discard-rule idea with one forward cursor).

def two_pointer(nums, target):
    lo, hi = 0, len(nums) - 1     # the two ends of the search space
    while lo < hi:                # INVARIANT: any answer is inside [lo, hi]
        if is_hit(lo, hi):        # ← DECIDE: hit test
            return (lo, hi)
        if move_low(lo, hi):      # ← DECIDE: move rule
            lo += 1
        else:
            hi -= 1
    return None

Solving a problem = filling the two blanks. For two-sum on a sorted array: is_hit is nums[lo] + nums[hi] == target, and move_low is nums[lo] + nums[hi] < target (a too-small sum can only grow by raising the left end, so the left value is discarded safely). The invariant fixes everything else.

Walkthrough

Opposite-direction pair sum on a sorted array, target 16. Each step either grows the sum (move L right) or shrinks it (move R left) — never skipping a valid pair.

Problems

names link to my write-ups as I solve them — the list is the curriculum, the links are progress.

When it fails

• Input isn’t sorted and there’s no budget to sort. The ordering the pointers exploit is gone — reach for a hash-table with O(1) seen-state lookups instead.
• You need every pair/triple, not one. Two pointers only helps as the inner loop after a sort (that is exactly how 3Sum works); a lone sweep won’t enumerate them.
• The ends aren’t monotone in what you compare. If a move doesn’t provably discard a candidate, the invariant is broken — rethink the discard rule or switch tools.

Related

• Sliding window — the same-direction specialization: both pointers move forward and the gap between them is the window.
• Binary search — also bounds a range from two sides, but halves on a monotone predicate rather than stepping one index at a time.
• hash-table — the fallback when the array can’t be ordered but you still need fast pair lookups.
• In production: two converging cursors over sorted runs is a merge — LSM-tree compaction merging sorted SSTable runs, and a sorted-merge stream join advancing whichever side is behind. Same invariant: whatever a cursor passes is never revisited.

Pattern DNA