Two Pointers

Two pointers turn nested loops into linear scans by maintaining a small set of indices and an invariant about the region between them.

Pattern 1: Opposing pointers on sorted or symmetric data

Use when: array is sorted or you compare symmetric positions.

Invariant: all pairs outside [l,r] are already decided.

Skeleton:

l, r := 0, len(nums)-1
for l < r {
    // evaluate nums[l] + nums[r] or compare
    // move one pointer to restore invariant
}

Used by:

• two-sum-ii (sorted sum)
• container-with-most-water (move shorter side)
• valid-palindrome (skip non-alnum)

Pattern 2: Slow/Fast pointers for filtering

Use when: you need to keep/remove elements in-place or check subsequences.

Invariant:

• slow is the length of the kept prefix.
• fast scans the input once.

Skeleton:

slow := 0
for fast := 0; fast < len(s); fast++ {
    if keep(s[fast]) {
        s[slow] = s[fast]
        slow++
    }
}

Used by:

• is-subsequence (advance slow when match)
• reverse-string (swap ends)

Pattern 3: Three-way partition (Dutch flag)

Use when: partition array into <, =, > regions in one pass.

Invariant:

• [0..low-1] < pivot, [low..mid-1] == pivot, [high+1..end] > pivot.

Skeleton:

low, mid, high := 0, 0, len(nums)-1
for mid <= high {
    switch nums[mid] {
    case 0: swap(low, mid); low++; mid++
    case 1: mid++
    case 2: swap(mid, high); high--
    }
}

Used by:

• sort-colors

When to use Two Pointers (checklist)

• Input is sorted or can be sorted without breaking requirements.
• You need to shrink/expand a range while preserving an invariant.
• You need linear-time in-place filtering or partitioning.

Common failures (checklist)

• Moving the wrong pointer (breaks invariant).
• Forgetting the 1-indexed output in two-sum-ii.
• Not skipping duplicates in 3sum.

Problem mapping

• valid-palindrome: opposing pointers with skips.
• is-subsequence: slow/fast across two strings.
• two-sum-ii: opposing pointers on sorted array.
• container-with-most-water: move the shorter side.
• 3sum: sorted + two-sum inner scan + dedupe.
• sort-colors: Dutch flag partition.
• reverse-string: symmetric swaps.