Two Pointers

Reader guide and study workflow · Complete course map

Given sorted values [1,3,5,8,10], find two distinct positions whose values total 9. Draw one candidate for every pair of positions before reaching for a named technique.

Turn one comparison into a proof

Trying every pair is a correct starting model, with n(n-1)/2 candidates. A map could remember earlier values, but sorted order may let us avoid both the pair enumeration and the extra storage.

Compare the widest remaining pair, 1 and 10. Their sum is 11. Why remove 10 rather than 1? Every other available partner of 10 is at least 1, so every pair retaining 10 has sum at least 11. One comparison rules out an entire group. The next pair, 1 and 8, reaches 9.

The reusable state is the smallest and largest still-possible indices. Before each comparison, any valid answer must lie entirely between them. A too-small sum similarly rules out the left endpoint, since its largest available partner was already too small. Each justified discard reduces the remaining interval; that is where linear work comes from.

Try the same movement on unsorted [3,2,4], target 6. Comparing 3+4 and discarding 4 would lose the actual pair 2+4. The proof, not the pointer syntax, tells you sortedness matters. Water containers also discard endpoints, but need a different bound and do not require sorted heights. Use the workshop to separate these reasons before using the reference patterns.

Prerequisites and readiness

Know sorted order, index versus value, exclusive slice endpoints, and shared slice mutation. You are ready to leave when you can justify a pointer move by naming every candidate it discards, not by saying that two pointers are faster.

Reasoning workshop: prove the discard

Pair grids explain linear search

Imagine a cell for each pair of indices i<j. A brute-force two-sum search examines every cell. On sorted input, comparing the smallest and largest remaining values lets you remove an entire row or column. With [1,2,4,8], target 6, the pair 1+8 is too large: replacing 1 with a larger remaining left value cannot rescue the endpoint 8. Remove 8. Then 1+4 is too small: replacing 4 with a smaller partner cannot rescue 1. Remove 1. The remaining 2+4 is the answer, with indices [2,3] because this interface is one-based.

This proof depends on sortedness. Sorting an unsorted Two Sum input would destroy its original indices unless you carried them along; that is why the hash-map version in another module is not interchangeable with this one.

A different discard: water containers

For heights [1,8,6,2,5,4,8,3,7], the first area is 1*8=8. Keeping the height 1 and moving the other endpoint inward cannot improve it: width decreases and limiting height cannot exceed 1. This discards the left endpoint, not the taller endpoint. The next pair has area 7*7=49. Equal endpoint heights allow either side to move, because either fixed endpoint is bounded by the area already checked.

Do not overstate this as “moving the shorter side increases the area.” It may decrease the area. The claim is that discarded pairs cannot beat the best already seen. This difference between immediate improvement and safe elimination is the heart of many greedy proofs.

Matching is not partitioning

A subsequence scan accepts the earliest available next byte. For s="aba", t="aabba", the matches can use positions 0, 2, and 4. Choosing an earlier match never removes room for later matches. A mismatch consumes text but does not reset the matched prefix. Palindrome comparison instead pairs surviving bytes from opposite ends after skipping punctuation. Neither algorithm sorts data or needs an output buffer.

Sort Colors uses a stronger four-region picture: zeros | ones | unknown | twos. On [1,2,0], after scanning the first 1, swapping the 2 with the unknown rightmost value gives [1,0,2]. The new middle 0 is still unknown, so mid cannot advance. Process it next to obtain [0,1,2]. The unknown-region length decreases on every iteration, including iterations where mid stays fixed.

Uniqueness and ownership

3Sum returns value triples, not index triples. [0,0,0,0] has four choices of three indices but only one answer triple. Skip equal anchors and equal pair values only after establishing the sorted search argument. The supplied reference sorts the caller's slice; copy it first only when a caller needs the original order. That copy changes auxiliary space and should be acknowledged.

Reverse String acts on bytes. Reversing UTF-8 bytes is not reversing displayed characters; changing the interface to runes would change the exercise. A double reversal is useful as a property test, but a no-op also passes it. Pair it with the direct position specification output[i]=original[n-1-i].

Pattern reference

Use these summaries after deriving the state and the reason each update is safe. The patterns name decisions already justified above.

Pattern 1: Opposing pointers on sorted or symmetric data

Use when: sorted order rules out endpoint pairs, symmetry fixes matching partners, or an endpoint gives a bound on every narrower candidate (water containers). Container heights need not be sorted.

Invariant: every discarded position has a task-specific justification: impossible sum, bounded area, or completed symmetric comparison. For the palindrome task, retain ASCII letters and digits, fold A–Z to a–z, and skip punctuation at both ends.

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: one sequence is scanned while a pointer records how much of a requested sequence has matched. This is the read-only relative of the Array & String compaction pattern.

Invariant: before reading text position j, s[:matched] is the longest prefix matched in t[:j], using earliest possible positions.

Skeleton:

matched := 0
for j := 0; j < len(t) && matched < len(s); j++ {
    if s[matched] == t[j] {
        matched++
    }
}
return matched == len(s)

Used by: is-subsequence. A mismatch consumes one text byte and retains the matched prefix. Neither string is modified. reverse-string instead uses opposing symmetric pointers and a mutable byte slice.

---

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 three-sum.

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.
• three-sum: sorted + two-sum inner scan + dedupe.
• sort-colors: Dutch flag partition.
• reverse-string: symmetric swaps.

Reconstruction lab

1. Why is “always move the taller wall” invalid? Trace heights [1,2,4,3].
2. Trace the four regions on [2,1,0], naming the unknown interval after each swap.
3. For [0,0,0,0], explain separately why equal anchors and equal pair values must be skipped.

Model answers

The first area for [1,2,4,3] is 3. Moving the taller wall repeatedly keeps height 1 and misses the optimal pair at indices 1 and 3, area 4. Moving the shorter endpoint exposes that pair.

Initially the whole array is unknown. Swap the first 2 with the last 0: [0,1,2], with indices 0..1 still unknown. Process 0, moving low and mid to 1. Process 1, moving mid to 2; unknown is empty. The 2 region began as soon as high moved left.

Repeated anchors would reproduce the same smallest value. Repeated inner values would reproduce the same remaining pair for one anchor. Both sources of duplication must be removed, while still allowing distinct indices holding equal values.

Problems in this module

• Valid Palindrome
• Is Subsequence
• Two Sum II - Input Array Is Sorted
• Container With Most Water
• 3Sum
• Sort Colors
• Reverse String

Interactive checkpoint

Open the Two Pointers quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

Learner experience: how to make this topic stick

The moves to recognize

How to practice without turning it into grind

Debugging instincts to build

A small way to make it memorable