Recognizing two pointers
Overview
Recognizing when to use two bounded iterators to prune a search space from O(n^2) to O(n).
The surface signal is a SORTED array (or one that can cheaply be sorted) where the problem asks about PAIRS satisfying a condition. One pointer starts at each end, moving based on a comparison, safely discarding rows/columns of invalid pairings without explicitly checking them.
Where used: Memory management protocols, like Cheney's Garbage Collection (Semispace Compaction), which uses a scan and an allocate pointer., Cycle detection (Floyd's Tortoise and Hare) in networked state machines.
Why learn this
- It differentiates the 'opposite-end convergence' pattern on sorted arrays from the 'fast/slow' pattern used for cycle detection.
- It teaches you to recognize distractors: unsorted problems where sorting destroys needed information (like original indices) cannot directly use two pointers.
Common mistakes
- Mixing up two-pointers with sliding window: Two pointers typically move from OPPOSITE ends toward each other over a sorted, static structure. Sliding window moves both pointers in the SAME direction over a contiguous range. They are distinct patterns.
Recall questions
- What strict precondition must usually be met to use the opposite-end convergence two-pointer technique?
- What is the primary recognition signal for the fast/slow (Tortoise and Hare) pointer variant?
Understanding checks
You are given an UNSORTED array of integers and asked to find two indices that sum to a target value. The problem explicitly states you must return the original array indices. Should you sort the array and use two pointers?
No. Sorting the array destroys the original indices required for the output. Because you cannot sort, the two-pointer technique is invalid here; a hash map should be used instead.
Recognizing when a pattern is structurally invalidated by constraints (like needing original indices) is critical for diagnosing the right approach.
A developer is using two pointers, starting at index 0 and moving both to the right, to find pairs that sum to K in a sorted array. Why is this structurally flawed for finding pairs?
Moving both pointers to the right is a sliding window mechanic, meant for contiguous subsets, not discrete pairs. For pairs in a sorted array, opposite-end convergence (one at 0, one at N-1) is required to systematically increase or decrease the sum.
Conflating the mechanical movement of sliding window with two pointers breaks the mathematical invariant that allows O(n^2) to be pruned to O(n).
Practice tasks
Fix the pointer movement
The given two-pointer implementation for finding a target sum in a sorted array moves the wrong pointers. Fix the comparison logic so it correctly converges from opposite ends.
Continue learning
Previous: Two pointers
Previous: Fast & slow pointers