Two Pointers

Pronunciation: TOO POYN-terz

Updated October 3, 20262 min read

In short

The two pointers technique walks an array or list with two indexes moved by simple rules, turning many problems that seem to need nested loops into one pass.

What is the two pointers technique?

A classic example is finding two numbers in a sorted array that add up to a target. Checking every pair takes O(n²) time. With two pointers, one starts at the left end and one at the right: if their sum is too small, move the left pointer right; if too big, move the right pointer left. Each step rules out many pairs at once, and the answer is found in one O(n) pass.

Pointers can also move in the same direction at different speeds. With fast and slow pointers, also called the tortoise and hare, the fast one moves two steps for every one of the slow one; in a linked list with a cycle they eventually meet, which is Floyd's cycle detection algorithm, and when the fast pointer reaches the end, the slow one is at the middle.

Other common uses include removing duplicates from a sorted array in place, reversing an array or string, merging two sorted lists, checking whether a string is a palindrome, and partitioning an array around a value as quicksort does. Most of these use O(1) extra memory, since they only keep a couple of indexes.

A common misconception is that two pointers works on any array. The opposite-ends version relies on the data being sorted, or on another rule that tells you which pointer to move. Without that, you can't safely skip pairs, and a hash map or a different approach is needed.

Key takeaways

Two pointers scan a sequence with two indexes in one pass.
Opposite-end pointers solve pair problems in sorted arrays in O(n).
Fast and slow pointers find cycles and the middle of linked lists.
It usually needs only O(1) extra memory.
It depends on sorted data or a rule for which pointer to move.

Example

Pair sum in a sorted array and a palindrome check (Python)python

def pair_with_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return nums[left], nums[right]
        if total < target:
            left += 1        # need a bigger sum
        else:
            right -= 1       # need a smaller sum
    return None

def is_palindrome(text):
    chars = [c.lower() for c in text if c.isalnum()]
    i, j = 0, len(chars) - 1
    while i < j:
        if chars[i] != chars[j]:
            return False
        i, j = i + 1, j - 1
    return True

print(pair_with_sum([1, 3, 4, 6, 9, 11], 13))   # (4, 9)
print(is_palindrome("Was it a car or a cat I saw?"))  # True

Readers ask

When should I use the two pointers technique?

When a problem involves pairs, ranges or comparisons in a sorted array or a linked list, and a brute-force solution would use nested loops. It often reduces O(n²) to O(n).

What is the difference between two pointers and sliding window?

A sliding window is a special case of two pointers where both move in the same direction and the elements between them form a window whose contents you track, such as a running sum.

What is Floyd's cycle detection?

An algorithm that detects a loop in a linked list with a slow pointer moving one step and a fast pointer moving two. If there is a cycle, the fast pointer eventually catches up with the slow one.