Two Pointers
Curriculum
A structured path to mastering the two pointers pattern. Redefine efficiency with two simultaneous thinkers.
What This Pattern Is Really About
Reduces nested loops by maintaining two positions and moving them based on a decision rule. O(n) is the new normal.
Each pointer movement eliminates possibilities that cannot be better than what remains. Search smart, not hard.
Elimination is valid when data has specific properties—usually sortedness—guaranteeing impossible outcomes.
Achieves O(n) time (each element visited once) and O(1) space (only track positions). Minimal footprint.
Mental Model & Invariant
Two pointers is a shrinking boundary.
"The region between your pointers contains all remaining possibilities; everything outside has been proven irrelevant."
Break this, and you lose the proof of correctness.
When It Holds
Before you start, after each movement, and at termination. If false, your algorithm is incorrect.
Decision Rule
Determines which pointer moves. Must guarantee eliminated region cannot contain better solution.
Termination
When pointers meet or cross, you've examined all possibilities and either found all solutions or determined none exist.
When to Think "Two Pointers"
sensorsStrong Signals
Array or string is sorted
Pairs or triplets with target property
Compare from opposite ends
Partitioning or rearranging in place
Longest/shortest sequence with constraint
Merging or comparing sorted sequences
ruleConstraint Signals
Must solve in linear time
Must use constant extra space
Cannot use additional data structures
Single pass through data required
Variants You Must Master
Opposite Direction
Start at opposite ends and move toward each other.
Solutions lie between current positions.
Fast–Slow
Both move same direction at different speeds.
Slow marks boundary of valid elements.
Sliding Window
Dynamic window expands and contracts.
Window satisfies constraint trackably.
Multi-Array
One pointer per array, advance by logic.
Unprocessed ahead of pointers.
How to Learn This Pattern
Identify the Invariant
Write down what must remain true at every step. What region contains all valid solutions? What does each pointer represent?
Define the Decision Rule
Determine when to move each pointer. What condition triggers left? Right? Why does this guarantee safe elimination?
Trace through by hand
Use a small example and manually execute your decision rule. Verify the invariant holds at each movement.
Verify Termination
Prove your algorithm finishes. Show at least one pointer moves closer to termination each step.
Check Edge Cases
Trace empty input, single element, duplicates, and boundaries. Verify the invariant holds.
Write Code
Translate your decision rule into code. If struggling, return to the invariant definition.
Canonical Problem List
auto_awesome_motionFoundation
Two Sum (sorted array)
Opposite pointers converging on target sum.
Valid Palindrome
Opposite pointers checking character equality.
Remove Duplicates
Same direction pointers marking valid boundary.
Move Zeroes
Fast-slow pointers partitioning elements in place.
Merge Sorted Arrays
Multi-array pointers combining sorted sequences.
auto_awesome_motionIntermediate
Container With Most Water
Opposite pointers with dynamic decision rule.
3Sum
Nested loop with two-pointer solving inner pair.
Array Intersection
Multi-array pointers finding common elements.
Trapping Rain Water
Opposite pointers tracking boundaries and volume.
Partition Array
Same direction pointers rearranging elements.
Squares of Sorted Array
Opposite pointers handling negative and positive.
auto_awesome_motionAdvanced
4Sum
Multiple nested loops with two-pointer optimization.
Median of Two Sorted Arrays
Multi-array pointers with complex termination.
Minimum Window Substring
Sliding window with character frequency tracking.
Reverse Words in String
Same direction pointers with multi-step rearrangement.
Non-Repeating Substring
Sliding window with hash map state.
Common Mistakes
Skipping the Invariant
Off-by-one errors, incorrect termination, pointer movements that violate constraints.
Write down the invariant in plain English before writing any code.
Moving the Wrong Pointer
Breaks the invariant; skips valid solutions or examines invalid regions.
Define the rule precisely: 'Move left if X, move right if Y'.
Forgetting Edge Cases
Works on happy path but fails with duplicates, empty input, or boundaries.
Trace through empty input, single element, and all duplicates first.
Incorrect Termination
Loop exits too early or too late; misses solutions or examines irrelevant regions.
Prove that at least one pointer moves closer to termination with each step.
Assuming Sorted Input
Decision rule relies on sortedness but problem doesn't guarantee it.
Verify the property or sort the input first. 'Two pointers != Sorted' always.
Interview Guidance
What they test
- →Decision Rule Justification
- →Invariant Articulation
- →Step-by-Step Tracing clarity
Strategy
Avoid "I'll use two pointers" without context. Instead: "I need to find pairs efficiently, so I'll maintain two positions and move them based on a specific rule that eliminates bad candidates."
The Verbal Template
"At every step, [property about pointers and search space] remains true."
"I move left when [condition] and right when [condition] to eliminate safe regions."
"Let's walk through this example. Here I check X, so I move Y pointer."
"When characters cross, all possibilities are exhausted."
When You've Mastered It
Immediate pattern identification
Invariant articulated before code
Verified edge cases analytically
Zero hesitation in decision rule
Adapting to problem variations
Flawless first-try implementation
What This Unlocks Next
Sliding Window
Extends boundary movement with window state tracking (contraction/expansion).
Binary Search
Same elimination logic, but divides the space instead of shrinking it linearally.
Greedy Algorithms
Embodying locally optimal choices for global results.
Graph Traversal
Applying fast/slow pointer logic for cycle detection and connectivity.