Two Pointers

Two-pointer triggers: The input consists of one or two arrays/strings/linked lists. We need to use O(1) extra memory or modify the input in place. The input is sorted. The naive solution is $O(n^2)$ and we want to get to $O(n)$.

Key Variations

There are generally three main ways to use the two pointers technique:

1. Inward Pointers (Converging)

One pointer starts at the beginning (left = 0) and the other at the end (right = n - 1). They move towards each other.

• When to use: Searching for a pair in a sorted array, checking for palindromes, reversing a string/array.
• Termination: Usually when left > right.

2. Slow and Fast Pointers (Same Direction)

Both pointers start at the beginning, but one moves faster than the other.

• When to use: Cycle detection in linked lists (Floyd's Cycle Finding Algorithm), removing duplicates in-place, sliding windows.
• Termination: Usually when the fast pointer reaches the end.

Seeker and Writer

In-place modification problems can get tricky when we need to read the elements from left to right and write them from left to right. For problems like this, we recommend using fast and slow pointers, except that each one has a specific role:

• The fast pointer is the seeker, looking for the next element to write.
• The slow pointer is the writer, staying at the position where the next element needs to be written.

Recipe: Seeker and Writer

seeker, writer = 0, 0
while seeker < len(arr):
    if we need to keep arr[seeker]:
        arr[writer] = arr[seeker]
        writer += 1
        seeker += 1
    else:
        seeker += 1

3. Parallel Pointers

Two pointers moving through two different arrays (or lists).

• When to use: Merging two sorted arrays, finding intersections between two sorted lists.
• Termination: Usually when one of the pointers reaches the end of its array.

Why Use It?

• Time Complexity: Often reduces a nested loop $O(n^2)$ solution to a single pass $O(n)$.
• Space Complexity: Usually efficient $O(1)$ constant space, as it only requires two variables.