Two Pointers — Two Positions, One Pass

What is it? #

The two-pointer technique keeps two positions in the data and moves them according to what it finds, instead of looping over every pair.

There are two main shapes. Opposite ends: one pointer starts at the beginning, the other at the end, and they move towards each other. Same direction: both start at the front and move at different speeds or for different purposes.

The payoff is turning an O(n²) nested loop into a single O(n) pass, usually with no extra memory.

The requirement is that you can decide which pointer to move based on what you see. For opposite-ends problems, that usually means the data is sorted.

Think of it like this #

Two people searching a long bookshelf for two books whose page counts add up to exactly 500. One starts at the thin end, the other at the thick end. If the total is too high, the person at the thick end steps back. If it is too low, the other steps forward. They meet in the middle having checked a fraction of the pairs.

Simple example #

Four problems that all collapse to one pass: finding a pair that sums to a target in a sorted list, checking a palindrome, removing duplicates in place, and merging two sorted lists.

Code #

# 1. Opposite ends: find two numbers summing to a target (sorted input)
def two_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            # need a bigger number
        else:
            right -= 1           # need a smaller number
    return None

print(two_sum_sorted([1, 3, 4, 7, 11, 15], 18))    # (2, 5)


# 2. Opposite ends: palindrome check with no extra memory
def is_palindrome(text):
    left, right = 0, len(text) - 1
    while left < right:
        while left < right and not text[left].isalnum():
            left += 1
        while left < right and not text[right].isalnum():
            right -= 1
        if text[left].lower() != text[right].lower():
            return False
        left, right = left + 1, right - 1
    return True

print(is_palindrome("A man, a plan, a canal: Panama"))    # True


# 3. Same direction: remove duplicates in place from a sorted list
def dedupe_sorted(nums):
    if not nums:
        return 0
    write = 1                        # where the next unique value goes
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1
    return write                     # length of the deduped prefix

values = [1, 1, 2, 3, 3, 3, 4]
length = dedupe_sorted(values)
print(values[:length])               # [1, 2, 3, 4]


# 4. Two lists: merge two sorted lists in one pass
def merge_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
        else:
            out.append(b[j]); j += 1
    out.extend(a[i:])
    out.extend(b[j:])
    return out

print(merge_sorted([1, 4, 9], [2, 5, 6]))     # [1, 2, 4, 5, 6, 9]


# 5. Fast and slow pointers: find the middle in one pass
def middle_value(items):
    slow = fast = 0
    while fast + 1 < len(items):
        slow += 1
        fast += 2
    return items[slow]

print(middle_value([10, 20, 30, 40, 50]))     # 30

How it works #

In two_sum_sorted, the decision rule is what makes it work. Because the list is sorted, a total that is too small can only be fixed by moving the left pointer right, and one that is too large by moving the right pointer left. Each move eliminates a whole set of pairs without checking them, so the scan is O(n) instead of O(n²).

is_palindrome compares characters from both ends inwards, skipping anything that is not a letter or digit. It uses no extra list, so memory is constant — an improvement over building a cleaned copy.

dedupe_sorted is the read/write pointer pattern. read scans every element; write marks where the next kept element belongs. Everything before write is the cleaned result. This in-place filtering pattern appears whenever you cannot afford a second array.

merge_sorted advances whichever pointer holds the smaller value. This is the merge step of merge sort, and it also merges sorted files, sorted database results and timelines.

middle_value moves one pointer twice as fast as the other. When the fast one reaches the end, the slow one is halfway. On a linked list, where you cannot compute the length cheaply, this is the standard trick.

The common thread: each pointer only ever moves forwards (or inwards), so the total number of moves is bounded by the length of the data.

Real-world use #

In-place deduplication and filtering matter when memory is tight or datasets are large — cleaning sensor readings, compacting logs, removing duplicate records from a sorted export.

Merging sorted streams is used constantly: combining sorted query results, merging time-ordered event feeds from several services, and external sorting of files too large for memory.

Any time you catch yourself writing a nested loop over the same array, pause and ask whether sorting first and using two pointers would work. Sorting costs O(n log n), and the scan is then O(n), which still beats O(n²) for large inputs.

The fast and slow pattern is also used to detect cycles in linked lists and in iterative sequences, as seen in the linked list lesson.

Common mistakes #

• Using opposite-ends pointers on unsorted data, where the movement rule no longer holds.
• Forgetting to advance a pointer in some branch, causing an infinite loop.
• Off-by-one errors at the boundaries — decide clearly whether the pointers may meet.
• Overwriting values with the write pointer before reading them.
• Using two pointers where a hash set is simpler, such as unsorted two-sum.

Practice #

Write a function that removes all instances of a value from a list in place and returns the new length. Then write one that, given a sorted list, returns all unique triples summing to zero using a fixed element plus two pointers. Finally, merge three sorted lists with pointers rather than concatenating and sorting.