Two Pointers
Two pointers can be employed or at least considered, when the movement of each pointer has a single-direction (monotonous) effect on some values:
For example, moving the right pointer forward only increases the sum whereas moving the left pointer forward only decreases the sum. Two pointers like this can be used effectively in Sliding Window problems. (Famously, @lee's solutions)
Two pointers can be used to perform traversal of data structures like arrays and linkedlists in efficient way (usually in O(N) amortized time)
Traversal Over Linkedlist
Having a slow pointer and fast pointer on a linked list with different starting positions, and then traverse synchronously.
A typical combination of the fast and slow pointers is: that the fast pointer moves twice as fast as the slow pointer, such as for cycle detection (Floyd's Cycle Detection). The idea is to have the fast pointer reach the end of the list first so that the status of the slow pointer becomes meaningful when the length of the list is not given initially.
Problems
Last updated