Two pointers is a competitive programming approach. In this method, two pointers are used to iterate through an array. Each pointer can only move to one direction (for example, one to the left from one end, the other to the right from the other).
Different variations include:
- Fast and slow pointers
- Left and right pointers — one starts at the beginning, the other starts at the end.
- Used for problems like two sum, finding pairs, or checking for palindromes.
- Sliding window
- Read and write pointers — for array or string manipulations.
- Twin pointers — two pointers traverse two separate structures simultaneously. Good for comparison problems.
Fast and slow pointers
One variation on two pointers is to have one pointer iterate slowly and the other iterate faster, called Floyd’s algorithm. This is especially helpful for working with linear data structures.
This is a powerful idea in general, because it basically ensures we can solve the question in a single pass instead of multiple. Having one pointer be ahead and another be behind — then moving each one (either by the same amount or with one moving by more).
For linked list questions:
- For cyclic questions, we use this because it’s guaranteed the fast and slow pointers will meet at some point, and it uses space complexity.
- To find the halfway element, we also do this because the slow pointer will reach the middle at the same time the fast pointer reaches the end.