Two Pointer

The two-pointer technique walks two indices through a sequence — usually one at each end, or both moving forward at different speeds — to solve problems in O(n) that look like they need O(n²). The standard interview tool for sorted-array problems.

Complexity

Best	Average	Worst	Space (Worst)
`Ω(n)`	`Θ(n)`	`O(n)`	`O(1)`

How it works

Place pointers at both ends of a sorted array. Compare what they index; based on the comparison, move the left pointer right or the right pointer left, monotonically shrinking the search space. Each pointer moves at most n times — total O(n).

Python implementation

def two_sum_sorted(arr, target):
    """Find two indices in a SORTED array that sum to target. O(n)."""
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)
        if s < target:
            lo += 1
        else:
            hi -= 1
    return None


def remove_duplicates_in_place(arr):
    """Remove duplicates from a sorted array in place. Returns new length."""
    if not arr: return 0
    write = 1
    for read in range(1, len(arr)):
        if arr[read] != arr[read - 1]:
            arr[write] = arr[read]
            write += 1
    return write


print(two_sum_sorted([1, 2, 4, 7, 11, 15], 13))   # (2, 4) — 4 + 11

a = [1, 1, 2, 3, 3, 4]
n = remove_duplicates_in_place(a)
print(a[:n])    # [1, 2, 3, 4]

Trade-offs

Turns O(n²) brute-force into O(n) for many sorted-array problems.
Often requires the input be sorted first (which itself is O(n log n)).
O(1) extra space — in-place transformations are natural.
Common patterns: two-sum (sorted), three-sum, container with most water, removing duplicates, palindrome check.

← Back to Algorithms