Card 08/ 08
Recap: Two Pointers
From both ends on sorted input for pairs and triples; read and write in one direction for rewriting in place.
Two pointers answer a pair question or rewrite an array in one pass, with O(1) extra space, by moving two indices so that every step settles a value for good. It comes in two forms, and each has its own cue and its own precondition.
- Opposite ends. The pointers start at both ends of a sorted array and move inward. A sum that is too small moves the left pointer, one that is too large moves the right, and no pair outside the pointers can be the answer.
- Read and write. Both pointers move forward. The read pointer visits every value and the write pointer marks the next slot for a value worth keeping, so the kept values close up in their original order and the write pointer's final value is the kept length.
The form, its cue, what it needs and what it costs, side by side:
| Form | Cue | Precondition | Moves | Cost |
|---|---|---|---|---|
| Opposite ends | A pair or triple with a target sum, or pairing under a limit | Sorted input | Left moves right when too small, right moves left when too large | O(n) time per pass, O(1) extra space |
| Read and write | Filter or compact an array in place, keeping order | None for filtering; sorted input to drop repeats in one pass | Read moves every step, write moves only when a value is kept | O(n) time, O(1) extra space |
Triples fix one value and run the pair search on the rest, at O(n²), skipping any value equal to the one before so that no triple is counted twice. A problem that never mentions a sum can still be a pair search from both ends, as pairing riders under a weight limit is. On unsorted input the opposite-ends search can walk past a pair that exists, so sort first at O(n log n), or use a hash map of complements when the original indices matter. In TypeScript, sort numbers with the comparator (a, b) => a - b.
← → move through sections and cards