Two pointers

When to reach for it

• The input is sorted, or you may sort it, and you need a pair or triple that meets a condition.
• You compare the start and end of something: palindromes, mirrored sequences, reversing in place.
• You must filter or rearrange an array in place with constant extra space.
• You walk two sorted sequences side by side: merging, diffing, finding common items.

The core idea

Each pointer marks an edge of the part of the input you still need to consider. Because the data is ordered, comparing the values under the two pointers tells you which side cannot be part of any answer, so you move that pointer and never look back. That one-way movement is why the whole pass costs O(n).

There are two shapes. Opposite ends: left starts at the first index and right at the last, and they move toward each other until they meet. Same direction: a slow pointer marks where the next kept element goes while a fast pointer scans ahead; everything before slow is finished output. Diffing two sorted lists is the same idea with one pointer in each list.

A Python template

def pair_with_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return left, right
        if total < target:
            left += 1          # too small: nothing pairs with nums[left]
        else:
            right -= 1         # too big: nothing pairs with nums[right]
    return None

def keep_in_place(nums, keep):
    """Move every element that passes keep() to the front, in order."""
    slow = 0
    for fast in range(len(nums)):
        if keep(nums[fast]):
            nums[slow] = nums[fast]
            slow += 1
    return slow                # length of the kept prefix

def common_sorted(a, b):
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            out.append(a[i]); i += 1; j += 1
        elif a[i] < b[j]:
            i += 1             # a[i] is too small to appear in b
        else:
            j += 1
    return out

Time and space

Each pointer moves in one direction only, so together they take at most n steps: O(n) time and O(1) extra space. If you sort first, the sort dominates at O(n log n). For triples, fix one element and run the pair search on the rest, which is O(n squared) overall: still a full factor of n better than three nested loops.

Common mistakes

• Running the opposite-ends version on unsorted data, where moving a pointer can skip the answer.
• Looping with left <= right when an element must not pair with itself.
• Forgetting to skip equal neighbors when the question wants unique triples, which reports the same answer several times.
• Returning indexes from a sorted copy when the question wants positions in the original array.
• Writing to slow before reading fast in a way that overwrites a value you have not moved yet.

How to explain it out loud

Say why a pointer may move, because that sentence is the proof that the algorithm is correct: "The array is sorted, so if the sum is too small, nothing can pair with the left value. I can drop it." Interviewers wait for it, and Devana's rubric scores it as logic explanation.

Before coding, state what is true about the data between or before your pointers. After coding, trace a short example with both pointers moving, then name the duplicate, empty and single-element cases and give O(n) time with O(1) space. Saying all of this unprompted is the difference between thinking out loud and answering questions when asked.