Two pointers

Two pointers are two indexes that move through a list, usually towards each other or in the same direction. On a sorted list they can replace a check of every pair. The time then grows in step with n, written O(n), instead of with n times n, written O(n²).

Finding a pair in a sorted list

You have a sorted list and a target. Is there a pair of values, at different positions, that adds up to the target? Checking every pair takes about n² / 2 additions (n times n, halved). Two pointers need at most n − 1 moves.

Put lo at the first index and hi at the last. While lo < hi, add the two values. If the sum is the target, you have found the pair. Otherwise, one pointer moves:

s = a[lo] + a[hi]
if s > target:
    hi -= 1          # a[hi] is too big for any partner
else:
    lo += 1          # a[lo] is too small for any partner

When the two pointers meet, no pair is left to check, and there is no answer. Writing the whole function is ARRS-P1.

Why it never skips the answer

Each move rules out one value for good. The proof is an invariant (CORR-2):

• Start. The window is the whole list, so the statement is true.
• Keep. Suppose a[lo] + a[hi] > target. Every other value in the window is at least a[lo], because the list is sorted. So a[hi] plus any partner in the window is too big, and a[hi] is in no pair. Dropping it keeps the statement true. The case “too small” is the mirror image.
• Finish. When lo = hi the window holds one value, which cannot make a pair on its own. So no pair exists.

Each pass moves lo or hi by one, so the window shrinks by one each time: at most n − 1 passes. The method needs the list to be sorted. On an unsorted list, sort first (O(n log n)) or use a set (BIGO-P1).

Pointers in the same direction

The other common shape has a slow pointer and a fast pointer, both moving right. The fast one reads every value. The slow one marks where the next value to keep should go. Removing repeats from a sorted list, in place:

def remove_repeats(a):
    w = 0                        # a[0..w-1] is the answer so far
    for r in range(len(a)):
        if w == 0 or a[r] != a[w - 1]:
            a[w] = a[r]
            w += 1
    del a[w:]                    # drop what is left over

w never passes r, so the writes never cover a value that has not been read yet. This is O(n) time and O(1) extra space. Calling a.remove(x) in a loop instead would be O(n²): each call can shift up to n values.

When to reach for two pointers

• The list is sorted, or can be sorted, and you want pairs that meet a condition.
• You need to change a list in place with O(1) extra space.
• You compare a sequence with its own reverse, as in palindromes (lesson 6).
• You merge two sorted lists, with one pointer in each (SORT-2).

Now try ARRS-P1, Two timings that match.