Two Pointers in Arrays and Strings

The Two Pointers technique is a cornerstone of algorithmic optimization. In the context of arrays and strings, it allows us to process data in a single pass ($O(n)$ time) with constant extra space O(1), often replacing brute-force nested loops that would otherwise take O(n^2).

By maintaining two indices that move independently based on logic, we can efficiently narrow down search spaces or modify data in-place.

1. Opposite Directions Pointers

The most classic application involves placing one pointer at the start (left) and one at the end (right). We then move them toward the center until they meet.

Case A: Search Space Reduction (Sorted Data)

When an array is sorted, we can use the relative values of the elements at both pointers to decide which one to move. If our current sum is too small, we move the left pointer to increase it; if too large, we move the right pointer to decrease it.

Example: Two Sum II (Sorted)

def two_sum(numbers, target):
    l, r = 0, len(numbers) - 1
    while l < r:
        s = numbers[l] + numbers[r]
        if s == target:
            return [l + 1, r + 1]
        elif s < target:
            l += 1
        else:
            r -= 1

Case B: Symmetry and In-place Modification

This is used for checking properties like palindromes or performing in-place swaps.

Common Problems:

• Valid Palindrome: Comparing characters from both ends.
• Reverse String: Swapping characters at l and r until they meet.
• Container With Most Water: Moving the pointer pointing to the shorter line to potentially find a taller one.

2. Two Pointers across Two Arrays

In some problems, you are given two separate arrays and need to merge or compare them. Here, each pointer tracks the current position in its respective array.

Case A: The "Merge" Logic

Used when you need to combine two sorted sequences into one.

Example: Merge Sorted Arrays

def merge(arr1, arr2):
    p1, p2 = 0, 0
    merged = []
    while p1 < len(arr1) and p2 < len(arr2):
        if arr1[p1] < arr2[p2]:
            merged.append(arr1[p1])
            p1 += 1
        else:
            merged.append(arr2[p2])
            p2 += 1
    # Append remaining elements
    merged.extend(arr1[p1:])
    merged.extend(arr2[p2:])
    return merged

3. Same Direction (Sequential) Pointers

While similar to a sliding window, this variation focuses on "reading" and "writing" pointers to modify an array in-place without using extra space.

Common Use Cases:

• Remove Duplicates: One pointer iterates through the array, while the other marks the position of the last unique element found.
• Move Zeroes: One pointer finds the next non-zero element, while the other keeps track of where the next non-zero should be placed.

Why this works

The magic of Two Pointers lies in its ability to exhaust possibilities without visiting them. By moving a pointer, you are effectively "discarding" a set of pairs or configurations that you know—mathematically—cannot be the solution, thus keeping the complexity linear.

When to apply this?

1. The input is sorted (or can be sorted without hurting complexity).
2. You need to find a pair/triple that meets a certain condition.
3. You are asked to modify an array in-place (e.g., "without allocating extra space for another array").
4. You are comparing two strings/arrays for subsequences or intersections.