A lesson from the data structures and algorithms bootcamp. About a 11 minute read.
Run two indices through the data instead of one and a nested scan collapses into a single pass. The pattern is easy to recognise and easy to get wrong, because what makes it CORRECT is never the two pointers themselves. It is an argument about what you are allowed to throw away, and if you cannot make that argument the technique is just a faster way to get the wrong answer.
CONVERGING: one pointer at each end, moving inward. Palindromes, pairs summing to a target in a sorted array, container with most water. OPPOSITE SPEEDS: both start at the front, one moving faster, which is the linked-list trick from earlier for the middle, a cycle, or the kth from the end. READ AND WRITE: both start at the front, the reader scans everything and the writer only advances when it keeps something, which is how you remove elements, deduplicate, or compact an array in place with no extra memory. Nearly every two-pointer problem is one of those three, and naming which one you are in is most of the work of writing it.
The rest of this lesson continues with 4 further sections. See the full curriculum.
Browse all 536 practice puzzles