Lesson 29 / 42

Two Pointers

Two indices moving through a sequence to replace a nested loop with a single pass.

Converging or chasing

Opposite ends: left and right move toward each other (sorted two-sum, palindrome, container with most water). Same direction: a slow and fast pointer (remove duplicates in place, cycle detection). Turns O(n^2) into O(n).

Sorted two-sum

If the sum is too small, only moving left up can help; too big, only moving right down.

def two_sum_sorted(a, target):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target:
            return [lo, hi]
        if s < target:
            lo += 1
        else:
            hi -= 1
    return []

Quick check: The opposite-ends two-pointer trick needs the array to be...

  • Sorted
  • All positive
  • Even length
Answer

Sorted — Sorted order is what lets you decide which pointer to move from the current sum.