Algorithm Cheat Sheet: Two Pointers

When dealing with arrays or lists, we tend to think in the single-threaded way and scan the array or list with one pointer. Sometimes working concurrently through two pointers can help make things more clear and efficient. For example, problems can thus be solved within one pass instead of two. In some cases, solutions can also involve much less space usage.

Markers

When scanning a sequence of elements, sometimes we need to go back and retrieve an element visited before and correlate it with the current element. It would be helpful if we can mark the position/index of that previous element to facilitate such retrospection. With one pointer as the scanner traversing the sequence, we can add another pointer as the marker and pin it to that interesting element visited before.

  1. One typical scenario is to extract substrings from a string. We apply a head pointer pinned on the beginning of a substring. We then use a tail pointer to scan each element after the head pointer until it reaches a separator (e.g., a space). The substring is then defined between the head (inclusive) and tail (exclusive) pointers. To move on to the next substring, we forward the head pointer to be right after the tail pointer (which is now at the position of the separator) and then repeat the same process.
int head = 0;
int tail = 0;
for (; tail <= s.size(); ++tail)
{
    if (tail == s.size() || s[tail] == ' ') // Include the last substring.
    {
        if (tail > head) // Handle the separator of multiple spaces.
        {
            string sub = s.substr(head, tail - head);
        }
        head = tail + 1;
    }
}
  1. Another scenario is sequence reorganization. For an optimized space usage, we reorganize the elements of a sequence in-place by overwriting the original elements. Specifically, we let one pointer track the next position available for overwriting (as a marker) while rely on another pointer to scan each element. Examples:

  2. Sometimes both pointers are used as markers interchangeably. They are placed on each side of the sequence and then move towards each other. With the help of two pointers, problems are often able to be solved in linear time. Examples:

  3. In some cases the two pointers can be both markers and scanners. They define a certain size of window and then side that window. Examples:

  4. Two pointers can be extended to three pointers or more. For example, while we are using one pointer to scan each element, there can be two markers. Examples:

Fast and slow pointers

The two pointers don’t need to proceed under the same pace. For example, while the slow pointer scans the elements one by one, the fast pointer can cover two elements each time.

Middle element

With that, we can easily locate the middle element of a linked list within one pass. Since the fast pointer advances twice faster as the slow pointer, once it reaches the end of the linked list, the slow pointer will arrive in the middle of that list.

slow = head;
fast = head->next;
while (fast && fast->next)
{
    slow = slow->next;
    fast = fast->next->next;
}
return slow;

Linked list cycling

Fast and slow pointers can also be effective in determining the existence of cycling for a linked list. We let both pointers start from the head of the linked list. Because the fast pointer advances twice faster as the slow pointer, if the linked list ends up with cycling, they will eventually meet in that cycle. To prove it, since the fast pointer is faster, at some time it will catch up or pass the slow pointer. Let’s say at a certain moment, the fast pointer is one step behind the slow pointer. Then in the next round, the slow pointer moves one step further while the fast pointer moves two steps ahead, and then they meet. For another case, if the fast pointer is two step behind the slow pointer, then in the next round, it will become one step behind–the exactly same case we just discussed.

If we are also interested in learning the starting point (\(P_{start}\)) of the cycle, we can simply move the fast pointer back to the head of the linked list after their first meet. We then let both pointers continue going, but limit the fast pointer’s pace to be one step as well. The two pointers will meet again and the first position where they meet is the starting point of the cycle. Now let’s prove. When the two pointers meet for the fist time (say at \(P_1\)), because the fast pointer is twice faster, it also has traversed the twice distance (say \(2S\) steps) as the slow pointer (say \(S\) steps). The fast pointer then restarts from the head of the linked list and starts moving with the same pace as the slow pointer. They are guaranteed to meet at \(P_1\) (which might not be \(P_{start}\)) after another \(S\) steps. This is because at that moment, the fast pointer has traversed \(S\) steps from the head while the slow pointer has traversed accumulatively \(2S\) steps, which is similar to the situation of their first meet. Since both pointers advance with the same pace and eventually meet, the first position where they meet is the starting point of the cycle. Examples:

Alternatively, we can just use one pointer to scan the linked list, but reply on a hash table to remember each element visited. Once we encounter an element that is already in the hash table, we know cycling exists and that element is the starting point of the cycle. In comparison, using fast and slow pointers seems to involve more complex logic and implementation. However, with fast and slow pointers, the space usage is optimized (\(O(1)\)) whereas the hash table introduces the additional space with the size of the whole linked list in the worst case (when the cycle contains only one element).

Contents