Lesson 12 of 16 · 8:18
Two pointers
Two pointers are useful when a decision about one position lets you rule out many pairings or when one scan can both read and rewrite data. The pattern is not simply “use two variables.” Its value comes from monotonic movement and a proof that skipped candidates cannot be answers.
There are three common shapes: pointers moving inward from opposite ends, read and write pointers moving in the same direction, and fast/slow pointers whose relative motion reveals structure. Identify the shape from the guarantee you need.
What you should be able to do after this lesson
- Prove why a pointer move is safe
- Define the region each pointer owns
- Bound total movement rather than counting nested syntax
The mental model
The comparison at left and right must prove that one entire class of pairs cannot work. Move the pointer whose side has just been ruled out.
Recognize it when: Look for sorted pair sums, palindrome symmetry, partitioning, deduplication, merging, or a fast/slow relationship within one sequence.
The invariant to say aloud: Every candidate outside the active pointer region has already been proved impossible, completed, or copied into its final position.
Learn the ideas one at a time
Concept 1 of 4
Opposite ends
Watch from 0:00 ↗Start left at the smallest and right at the largest. On a sorted array, a sum that is too small can only be repaired by increasing left; too large by decreasing right.
Sorted order connects the current result to a safe movement. For a target sum, if left + right is too small, pairing left with any smaller right cannot help, so left can be discarded. If the sum is too large, right can be discarded symmetrically.
Walk through an example
In [1,3,4,8] for target 7, 1+8 is too large, so move right to 4. Then 1+4 is too small, so move left to 3. Now 3+4 succeeds.
In an interview
Explain the eliminated set of pairs after every move. Without sorted order or another monotonic property, the elimination proof may not exist.
Concept 2 of 4
Same direction
Watch from 0:00 ↗A read pointer scans every item while a write pointer marks the next output position. This supports stable filtering, deduplication, and in-place compaction.
A read pointer examines every input item while a write pointer identifies the next output slot. The prefix before write is the finished compacted result; the region from write to read contains disposable or stale values; the suffix after read is unseen.
Walk through an example
Remove zeros from [0,2,0,3]: read skips the first zero, writes 2 at index 0, skips the next zero, and writes 3 at index 1. The valid output prefix is [2,3].
In an interview
State whether relative order must be preserved. A stable write pointer preserves it; swapping with the end may be faster but changes order.
Concept 3 of 4
Fast and slow
Watch from 0:00 ↗Different speeds expose cycles, midpoints, or a fixed gap. The proof depends on relative motion, not merely using two variables.
Different pointer speeds encode distance. In a linked list, fast moving two edges while slow moves one either reaches the end, placing slow near the midpoint, or laps slow inside a cycle. Other variants maintain a fixed gap so one pointer trails another by k nodes.
Walk through an example
In a cycle, once both pointers are inside, fast gains one node per step relative to slow. With a finite cycle length, that relative position must eventually become zero and the pointers meet.
In an interview
Describe the relative-motion argument. Merely citing Floyd's algorithm does not prove why meeting indicates a cycle.
Concept 4 of 4
Why it is O(n)
Watch from 0:00 ↗Each pointer moves monotonically and at most n times. Nested-looking movement can still be linear when total pointer advances are bounded.
Two pointers can appear inside a nested loop and still be linear when neither moves backward. Count pointer advances across the whole run. If left advances at most n times and right advances at most n times, the total is at most 2n.
Walk through an example
A repair while-loop may advance left several times during one right step, but every element leaves the active region once. Those advances cannot be repeated later.
In an interview
Use an aggregate argument: each pointer crosses each position at most once. This is stronger than calling the loop “basically linear.”
Before you call this lesson done
- Identify the pointer geometry
- Write the discarded-candidate proof
- Name the completed region
- Count total monotonic advances
