Two Pointers

What “two pointers” means

A pointer here is just an index: a variable that holds a position in a list, like left = 0. The two pointers technique keeps two such indices moving over the same list at the same time, and uses their combined position to decide what to do next. Instead of a nested loop that pairs every item with every other item, we walk two markers across the list once and let their relationship carry the information a second loop would have re-discovered.

That single change is what turns some O(n^2) scans into O(n). Recall from the Big-O lesson that O(n^2) means the work grows with the square of the list size: double the list and the work quadruples, because a nested loop compares roughly n items against n items. O(n) means the work grows in step with the list: double the list, double the work. When two pointers between them touch each position only a constant number of times, the whole pass is O(n).

There are two common shapes:

• Opposite ends (converging). One pointer starts at the front, the other at the back, and they move toward each other until they meet.
• Same direction (fast/slow). Both pointers start at the front; a “read” pointer races ahead scanning every item while a “write” pointer lags behind, building the answer in place.

The rest of this lesson works through both.

Opposite ends: two-sum on a sorted array

Suppose we have a sorted list and a target number, and we want to know whether two of its values add up to that target. The brute-force way tries every pair: for each item, look at every later item and check the sum. That is a nested loop, O(n^2).

Because the list is sorted, we can do far better with one pointer at each end. Put left at index 0 (the smallest value) and right at the last index (the largest value). Look at nums[left] + nums[right]:

• If the sum equals the target, we found our pair.
• If the sum is too small, we need a bigger sum. The only way to grow it is to raise the small end, so move left up by one.
• If the sum is too big, we need a smaller sum, so move right down by one.

Each step throws away exactly one value that cannot be part of any solution, so the two pointers march toward each other and the scan finishes in one pass.

def two_sum_sorted(nums: list[int], target: int) -> tuple[int, int] | None:
    left = 0                       # smallest value, at the front
    right = len(nums) - 1          # largest value, at the back
    while left < right:            # stop when the pointers meet
        total = nums[left] + nums[right]
        if total == target:
            return (left, right)   # found a pair of indices
        elif total < target:
            left += 1              # too small: raise the low end
        else:
            right -= 1             # too big: lower the high end
    return None                    # pointers crossed; no pair sums to target

nums = [2, 7, 11, 15]
print(two_sum_sorted(nums, 9))    # -> (0, 1)
print(two_sum_sorted(nums, 26))   # -> (2, 3)
print(two_sum_sorted(nums, 100))  # -> None

Why is it safe to discard a value forever? Say the sum is too small. nums[left] is the smallest value still in play, so it pairs worst with right; every other partner it could take (right - 1, right - 2, and so on) is smaller and would only make the sum even smaller. So nums[left] can never reach the target with anyone, and we drop it by advancing left. The mirror argument justifies dropping right when the sum is too big.

Step-by-step trace

Walk two_sum_sorted on a target of 12, with the indexes written above each value so the pointers are easy to follow.

index:   0   1   2   3   4
value:   1   3   5   8   11

Each row shows the state at the start of a round: the current left, right, the two values they point at, their sum, and the decision that follows.

That target lands immediately. Now trace a target of 9, which takes several moves and shows the pointers converging:

And a target of 100, which no pair can reach, so the loop ends when the pointers meet:

When left reaches right the region between them is empty, the condition left < right becomes false, and the function reports None.

Complexity. Each round moves one pointer inward by one, and the pointers can close a gap of n at most n times, so the scan is O(n) time. We keep only the two integer markers, so it is O(1) space — a clean win over the O(n^2) nested-loop version.

Opposite ends: checking a palindrome

The same converging idea checks whether a sequence reads the same forwards and backwards — a palindrome, like "racecar" or the list [1, 2, 3, 2, 1]. A palindrome means the first item equals the last, the second equals the second-to-last, and so on inward. So compare the two ends and walk toward the middle.

def is_palindrome(s: str) -> bool:
    left = 0
    right = len(s) - 1
    while left < right:            # meet in the middle
        if s[left] != s[right]:    # a mismatched pair rules it out
            return False
        left += 1                  # step both pointers inward
        right -= 1
    return True                    # every pair matched

print(is_palindrome("racecar"))   # -> True
print(is_palindrome("hello"))     # -> False
print(is_palindrome("noon"))      # -> True

Here both pointers move on every step, so at most n / 2 comparisons cover the whole string: still O(n) time and O(1) space. Note this needs no sorted input — the requirement is symmetry, not order. Two pointers apply whenever a problem has a useful structure the pointers can exploit, and here the structure is the mirror.

Same direction: a read pointer and a write pointer

The second shape uses both pointers moving the same way. A read pointer scans every item front to back; a write pointer lags behind and marks where the next kept item should go. This lets us rebuild a list in place — reusing the same array rather than allocating a new one — which keeps the space at O(1).

Take removing duplicates from a sorted list so each value appears once. Since the list is sorted, duplicates sit next to each other, so an item is a duplicate exactly when it equals the item just before it. The write pointer holds the end of the “kept” prefix we are building; whenever the read pointer finds a value different from the last kept one, we copy it into the write slot and advance the writer.

def remove_duplicates(nums: list[int]) -> int:
    if not nums:                       # empty list: nothing kept
        return 0
    write = 0                          # nums[:write+1] is the deduped prefix
    for read in range(1, len(nums)):   # read scans from the second item on
        if nums[read] != nums[write]:  # a new value, not a repeat
            write += 1                 # make room in the kept prefix
            nums[write] = nums[read]   # place the new value
    return write + 1                   # length of the deduped prefix

nums = [1, 1, 2, 2, 2, 3, 4, 4]
length = remove_duplicates(nums)
print(length)                # -> 4
print(nums[:length])         # -> [1, 2, 3, 4]

We return a length rather than a new list because the work happens in place: the first length items of nums now hold the deduped values, and the caller slices nums[:length] to read them. The tail of the list still holds leftover values, which is why we report where the meaningful prefix ends.

Same direction: moving zeroes to the end

The same read/write pair solves “move all zeroes to the end while keeping the other values in their original order.” The write pointer marks where the next non-zero value belongs; the read pointer scans, and every time it meets a non-zero value it writes it to the front region. After the scan, whatever slots remain get filled with zeroes.

def move_zeroes(nums: list[int]) -> None:
    write = 0                          # next slot for a non-zero value
    for read in range(len(nums)):      # scan every item
        if nums[read] != 0:
            nums[write] = nums[read]   # pack non-zeroes toward the front
            write += 1
    for i in range(write, len(nums)):  # fill the rest with zeroes
        nums[i] = 0

nums = [0, 1, 0, 3, 12]
move_zeroes(nums)
print(nums)                  # -> [1, 3, 12, 0, 0]

In both cases the read pointer visits each of the n items once and the write pointer only ever moves forward, so the total is O(n) time and O(1) extra space. The list is transformed without a second array.

The precondition that makes it valid

Two pointers is not a trick you can drop on any problem. It works only when the list has a structure the pointer moves can rely on — usually one of:

• Sortedness, as in two-sum-on-sorted and remove-duplicates. Moving left up is guaranteed to raise the sum only because the list is ordered. On an unsorted list that guarantee is gone: nums[left + 1] might be smaller than nums[left], so advancing a pointer no longer moves the sum in a known direction, and discarding a value could throw away part of a real answer.
• Symmetry, as in the palindrome check, where the meaningful relationship is between mirror positions rather than sorted order.

The general name for the property is monotonic: as a pointer moves one way, the quantity you care about changes in one consistent direction, never reversing. That monotonic behavior is exactly what lets a single comparison rule out a value for good. Remove it and the technique gives silently wrong answers — it does not error, it just trusts a structure that is not there. If your input is unsorted but the problem needs order, you must sort first (an O(n log n) step) before two pointers apply.

Common pitfalls

• Wrong loop condition on converging pointers. Two-sum needs left < right, because pairing a value with itself is not a real pair. Using left <= right would let both pointers land on the same index and add a value to itself.
• Forgetting to move a pointer. Every branch of a converging loop must advance left or right. If some case leaves both untouched, the sum never changes, the condition never turns false, and the loop runs forever.
• Applying it to unsorted data. Two-sum-on-sorted and dedup assume order. Running them on an unsorted list returns wrong answers with no warning. Sort first, or reach for a different tool such as a hash set.
• Confusing the write pointer with a length. In the read/write pattern, write is an index. Remove-duplicates returns write + 1 because a length is one more than the last index. Off-by-one here silently drops or duplicates the final item.
• Assuming the tail is cleared. After an in-place dedup, items past the returned length are stale leftovers, not deleted. Only nums[:length] is meaningful; do not read past it.

Big-O summary

Practice

1. Write two_sum_sorted from scratch without looking above, then test it on an empty list [], a two-item list [1, 4] with target 5, and a list where no pair works. Confirm it returns None when there is no answer.

2. Adapt the palindrome check to ignore case and non-letters, so that "A man, a plan, a canal: Panama" counts as a palindrome. (Hint: skip a pointer forward while the character it points at is not a letter, using str.isalnum and str.lower.)

3. Rewrite move_zeroes so it uses a swap between the read and write pointers in a single pass instead of a second fill loop, and check it still produces [1, 3, 12, 0, 0] from [0, 1, 0, 3, 12].