Two pointers and index pointers

Many array problems can be solved by tracking two positions instead of one. Checking every pair of elements costs O(n²). A pair of pointers that each move in a predictable direction, and never backtrack, gets the same answer in O(n).

Two pointers on sorted data

Suppose you have a sorted array and want to find two elements that add to a target. Checking every pair works, but there is a faster way once the array is sorted.

Put one pointer at the start and one at the end. If the two values sum to less than the target, move the left pointer right, since every value to its left is smaller and would only make the sum smaller still. If they sum to more than the target, move the right pointer left, for the matching reason. Stop when you find the target or the pointers meet.

Each pointer only ever moves in one direction and can move at most n times in total, so the whole search is O(n). This only works because the array is sorted: without an order to rely on, moving a pointer past a value could skip the answer.

Try it on [2, 7, 11, 15] with target 9. Left starts at 2, right at 15, and the sum is 17, too large, so right moves to 11. Sum is 13, still too large, so right moves to 7. Sum is 9, found in three steps.

1def two_sum(arr, target):2    left = 03    right = len(arr) - 14    while left < right:5        s = arr[left] + arr[right]6        if s == target:7            return (arr[left], arr[right])8        elif s < target:9            left += 110        else:11            right -= 112    return None13
14
15print(two_sum([2, 7, 11, 15], 9))16print(two_sum([1, 3, 5, 7], 8))

(2, 7)
(1, 7)

Read and write pointers

A different pair of pointers moves at different speeds through the same array. Removing duplicates from a sorted array in place is the standard example: a read pointer scans every element, and a write pointer only advances when it finds a value the write pointer has not already recorded.

Take [1, 1, 2, 2, 3]. The write pointer starts at index 0, holding the value 1. The read pointer checks index 1: still 1, matches what write already holds, so read moves on without writing. At index 2 the value is 2, which is new, so write advances to index 1 and stores it. The pattern repeats for the second 2 (skipped) and the 3 (written). By the time read reaches the end, the first three slots hold [1, 2, 3], the count of unique values.

1def remove_duplicates(arr):2    if not arr:3        return 04    write = 05    for read in range(1, len(arr)):6        if arr[read] != arr[write]:7            write += 18            arr[write] = arr[read]9    return write + 110
11
12arr = [1, 1, 2, 2, 3]13length = remove_duplicates(arr)14print(arr[:length])

[1, 2, 3]

Pointers closing in from both ends

A third pattern starts one pointer at each end of the array and walks them toward each other, swapping as they go. This reverses the array in place with no extra storage: swap the two ends, then move each pointer one step inward, and stop once they meet or cross.

1def reverse_array(arr):2    left = 03    right = len(arr) - 14    while left < right:5        arr[left], arr[right] = arr[right], arr[left]6        left += 17        right -= 18    return arr9
10
11arr = [1, 2, 3, 4, 5]12print(reverse_array(arr))

[5, 4, 3, 2, 1]

The same closing-in idea shows up outside arrays. Cycle detection on a linked structure moves one pointer one step at a time and another two steps at a time; if the fast pointer ever catches the slow one, there is a cycle. It is a different data structure, but the same core trick: two positions advancing at different rates until they meet.

Shrinking windows

When a problem asks for a subarray that satisfies some condition, two pointers can maintain a window instead of checking every possible subarray. Expand the right pointer to bring in more elements, and once the window meets or breaks the condition, move the left pointer to shrink it back. Each pointer still only moves forward, so the whole scan stays O(n).

Three pointers for three values

The two-sum pattern extends to three values by fixing one element and running the two-pointer scan on the rest. Sort the array first. For each index i, treat arr[i] as fixed and look for two more values, from the remainder of the array, that sum with it to the target; that inner search is exactly the two-pointer scan from before, run on the slice after i. The outer loop runs n times and the inner scan is O(n), so the whole thing costs O(n²), still far better than the O(n³) of checking every triple directly. This "fix one, two-pointer the rest" move generalizes further: fixing two elements and two-pointering the remaining pair solves the four-value version in O(n³), at the cost of one more nested loop each time you fix one more value.

Getting these right

Both pointers have to make guaranteed progress, or the technique breaks down. If you move both pointers in the same direction, or move the wrong one, you can loop forever or skip past the answer. Check, for every step, which direction each pointer is allowed to move and why.

The sorted-data trick only works because the array is sorted. On unsorted data, moving the left pointer past a value can throw away a valid answer that happens to sit somewhere else in the array, since nothing guarantees the values increase as you scan right.

The read-write pattern is easy to get wrong at the boundary. Initialize the write pointer to the first index, not one past it, or you will skip recording the very first value.

Two pointers are worth reaching for whenever a problem is about pairs, splits, in-place rearrangement, or a moving window. Once you notice one of these shapes, the pointer pattern usually falls out on its own.