Two Pointers

Overview

The two-pointer technique uses two indices that move through a sequence to avoid nested loops. A common pattern places one pointer at each end and moves them inward, often on a sorted array. It typically turns an O(n^2) brute-force scan into an O(n) solution with O(1) extra space.

Syntax / Usage

Start with pointers at the two ends and compare their values to decide which pointer to move. This works well for pair-sum and palindrome checks on ordered data.

def pair_sum_sorted(numbers, target):   # O(n) time, O(1) space; list must be sorted
    left, right = 0, len(numbers) - 1
    while left < right:
        current = numbers[left] + numbers[right]
        if current == target:
            return (left, right)
        if current < target:
            left += 1                    # need a larger sum
        else:
            right -= 1                   # need a smaller sum
    return None

Examples

Find two numbers in a sorted list that add up to a target:

print(pair_sum_sorted([1, 2, 4, 7, 11], 15))  # (2, 4) -> 4 + 11

Check whether a string is a palindrome by converging from both ends:

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

print(is_palindrome("racecar"))  # True

Common Mistakes

• Applying the converging-pointer pattern to unsorted data that requires sorting first.
• Using left <= right when the pointers should not overlap, causing double counting.
• Forgetting to move a pointer, which creates an infinite loop.
• Moving the wrong pointer and skipping over a valid answer.
• Returning values instead of indices (or vice versa) from what the problem asks.

See Also

algorithms-searching algorithms-sliding-window algorithms-sorting