A lesson from the Algorithms & Patterns module of the bootcamp. About an 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 recognize 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. 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. DIFFERENT SPEEDS: both start at the front and one moves faster, the linked list trick from earlier for finding 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 moves forward when it keeps something. That 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.
The rest of this lesson continues with 4 further sections. See the full curriculum.
Browse all 576 practice puzzles