The two pointers technique, from first idea to production

Seven prices, sorted from cheapest to dearest: 2, 5, 7, 9, 12, 16 and 21. You have a gift card worth exactly 25 and want two items that use all of it. You could try every pair. There are 21 of them, and with a thousand prices there would be almost half a million. Or you could put one finger on the cheapest item and one on the dearest, add them up, and move whichever finger the total tells you to. You’ll have the answer (9 and 16) after five looks, and with a thousand prices it would never take more than 999.

That second method is the two pointers technique. It’s one of the first patterns people learn for coding interviews, and it’s easy to file it under “interview trick” and move on. That would be a mistake. The same move, two positions walking through ordered data and one of them advancing at every step, is how PostgreSQL joins sorted tables, how databases sort data that doesn’t fit in memory, and how the AWS command line decides which files to upload and delete when this very site deploys.

By the end you’ll be able to solve the classic two-pointer problems, prove that your solution can’t miss an answer, use fast and slow pointers to find cycles in constant memory, partition an array in place, and recognize the merge step inside databases and sync jobs. Start at Beginner if “pointer” makes you think of C. If you’ve done a few LeetCode problems, skip to Intermediate, where the correctness argument lives.

Beginner: two fingers on one list

What a pointer is here

In this article a pointer is just a variable holding a position: an index into a list or string, or a reference to a node in a linked list. Nothing to do with memory addresses. “Two pointers” means you keep two of those positions at once and move them according to some rule, usually so that together they visit the data only once.

There are two common arrangements. The pointers can start at opposite ends and walk toward each other, which is what the gift card used. Or they can start at the same end and move in the same direction, one running ahead of the other. Beginner covers the first; Intermediate covers both.

Reversing a list in place

The smallest two-pointer program reverses a list without making a copy. Swap the first and last items, then the second and second-to-last, and keep going until the pointers meet in the middle.

def reverse_in_place(chars):
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]   # swap the two ends
        left += 1
        right -= 1
    return chars

print(reverse_in_place(list("pointer")))
print(reverse_in_place(list("ab")), reverse_in_place([]))
# ['r', 'e', 't', 'n', 'i', 'o', 'p']
# ['b', 'a'] []

Read the loop condition carefully, because it’s where most first attempts go wrong. left < right stops when the pointers meet (odd length, the middle item stays put) or cross (even length). Using left <= right would also work here, since swapping an item with itself is harmless, but in the problems below the difference matters, so it pays to decide deliberately every time.

Python strings can’t be changed, which is why the function takes a list of characters. In real Python code you’d write chars.reverse() or s[::-1]. Under the hood, CPython’s list.reverse() is this exact loop in C. From Objects/listobject.c:

static void
reverse_slice(PyObject **lo, PyObject **hi)
{
    assert(lo && hi);

    --hi;
    while (lo < hi) {
        PyObject *t = *lo;
        *lo = *hi;
        *hi = t;
        ++lo;
        --hi;
    }
}

Two pointers, swap, step inward, stop when they meet. The same twelve lines also do work inside Python’s sort, which reverses descending runs it finds in your data before merging them.

Is it a palindrome?

A palindrome reads the same forwards and backwards: “racecar”, or “A man, a plan, a canal: Panama” once you ignore case, spaces and punctuation. Checking one is reversal turned into a question. Compare the two ends; if they differ, the answer is no; if they match, step both pointers inward.

def is_palindrome(text):
    left, right = 0, len(text) - 1
    while left < right:
        if not text[left].isalnum():      # skip spaces and punctuation on the left
            left += 1
        elif not text[right].isalnum():   # ...and on the right
            right -= 1
        elif text[left].lower() != text[right].lower():
            return False                  # one mismatch is enough to say no
        else:
            left += 1
            right -= 1
    return True

for s in ["racecar", "A man, a plan, a canal: Panama", "ezychat", "", "No 'x' in Nixon"]:
    print(repr(s), is_palindrome(s))
# 'racecar' True
# 'A man, a plan, a canal: Panama' True
# 'ezychat' False
# '' True
# "No 'x' in Nixon" True

The skipping branches are the interesting part. Each pass through the loop moves exactly one pointer or both, never neither, so the loop always ends. And because each pointer only ever moves toward the middle, the whole check reads every character at most once. The obvious alternative, cleaned == cleaned[::-1], is shorter and perfectly fine in everyday code; it just builds two new strings to do it.

Pair sum in a sorted array

Back to the gift card. The problem: given a list of numbers sorted in ascending order and a target, find two of them that add up to the target.

The brute-force answer checks every pair. Here it is next to the two-pointer version, both counting how many sums they compute:

def pair_sum_brute(nums, target):
    checks = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            checks += 1
            if nums[i] + nums[j] == target:
                return (nums[i], nums[j]), checks
    return None, checks

def pair_sum(nums, target):
    """nums must be sorted ascending."""
    left, right = 0, len(nums) - 1
    steps = 0
    while left < right:
        steps += 1
        total = nums[left] + nums[right]
        if total == target:
            return (nums[left], nums[right]), steps
        if total < target:
            left += 1          # need a bigger sum: the only way up is to move left right
        else:
            right -= 1         # need a smaller sum: the only way down is to move right left
    return None, steps

prices = [2, 5, 7, 9, 12, 16, 21]
print(pair_sum_brute(prices, 25))
print(pair_sum(prices, 25))
print(pair_sum(prices, 4))
# ((9, 16), 17)
# ((9, 16), 5)
# (None, 6)

17 sums against 5, and when there’s no answer at all, 6 against all 21. Here’s every decision the two-pointer version made:

L=0 R=6   2 + 21 = 23  too small, left +1
L=1 R=6   5 + 21 = 26  too big, right -1
L=1 R=5   5 + 16 = 21  too small, left +1
L=2 R=5   7 + 16 = 23  too small, left +1
L=3 R=5   9 + 16 = 25  found

The rule fits in one sentence. If the sum is too small, move the left pointer right (to a bigger number); if it’s too big, move the right pointer left (to a smaller one). Because the list is sorted, those are the only two moves that can push the sum in the direction you need.

Each step moves one pointer one place closer to the other, so with n numbers there are at most n − 1 steps. That’s O(n), read “order n”: the work grows in a straight line with the input. The brute force does up to n × (n − 1) / 2 checks, which grows with the square of n, written O(n²). For 1,000 numbers that’s 999 steps against 499,500.

Step through it yourself. The array is editable; anything you type in pair-sum mode gets sorted first, because the technique depends on it.

Why it can’t miss

Speed is only half the story. The other half is that two pointers never skips the answer, even though it looks at so few pairs. The reason sits in each “discard”.

Take the first step: 2 + 21 = 23, too small. Twenty-one is the largest number in the list. So 2 plus anything in the list is at most 23, and therefore too small. The number 2 can’t be part of any answer, and throwing it away loses nothing. When the sum is too big, the mirror-image argument applies: the left number is the smallest left, so the right number plus anything is too big, and it can go.

Every step throws away one number with a reason like that. When the pointers meet, every number has been thrown away with a reason, so if they never found a pair, there wasn’t one. Intermediate turns this into a proper proof and shows the grid picture that makes it obvious.

Two pointers or a hash map?

There’s another famous way to solve pair sum: walk the list once and keep a dictionary of the numbers you’ve seen. For each number, check whether its partner, target - n, is already in the dictionary. That’s the Two Sum solution in the hash maps article, and it doesn’t need the input sorted.

So which is better? I measured both on a million random even numbers with an odd target, so there’s never an answer and both have to do the full walk (Python 3.13, my laptop, best of three runs):

import random, time, tracemalloc

def pair_sum(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
        else:
            right -= 1
    return None

def two_sum_hash(nums, target):
    index_of = {}
    for i, n in enumerate(nums):
        if target - n in index_of:
            return index_of[target - n], i
        index_of[n] = i
    return None

random.seed(7)
nums = [random.randrange(0, 10**9, 2) for _ in range(1_000_000)]   # all even...
target = 10**9 + 1                                                 # ...so an odd target never matches
sorted_nums = sorted(nums)

def measure(label, fn):
    start = time.perf_counter()
    fn()
    seconds = time.perf_counter() - start
    tracemalloc.start()
    fn()
    peak = tracemalloc.get_traced_memory()[1]
    tracemalloc.stop()
    print(f"{label:<31} {seconds * 1000:4.0f} ms  {peak / 2**20:5.1f} MiB extra")

measure("two pointers, already sorted", lambda: pair_sum(sorted_nums, target))
measure("hash map, unsorted", lambda: two_sum_hash(nums, target))
measure("sort a copy, then two pointers", lambda: pair_sum(sorted(nums), target))
# two pointers, already sorted     150 ms    0.0 MiB extra
# hash map, unsorted               180 ms   78.7 MiB extra
# sort a copy, then two pointers   308 ms   11.4 MiB extra

The speed is close to a draw in Python, because both are one pass of interpreted code. The memory is not. The hash map built a dictionary of a million entries, about 79 MiB, to answer a yes-or-no question. Two pointers used none. Sorting first doubles the time and copies the list.

My rule of thumb:

That last row is the one people forget. A hash map finds exact partners. Two pointers on sorted data can also answer “closest to the target”, “how many pairs are below it” and “every triple that sums to zero”, because order tells you which way to move when you miss.

def reverse_vowels(word):
    chars = list(word)
    vowels = set("aeiouAEIOU")
    left, right = 0, len(chars) - 1
    while left < right:
        if chars[left] not in vowels:
            left += 1
        elif chars[right] not in vowels:
            right -= 1
        else:
            chars[left], chars[right] = chars[right], chars[left]
            left += 1
            right -= 1
    return "".join(chars)

print(reverse_vowels("pointer"), reverse_vowels("Tarif"), reverse_vowels("xyz"))
# peintor Tiraf xyz

def closest_pair(nums, target):
    """nums sorted, at least two values. The pair whose sum is nearest to target."""
    left, right = 0, len(nums) - 1
    best = (nums[left], nums[right])
    while left < right:
        total = nums[left] + nums[right]
        if abs(total - target) < abs(sum(best) - target):
            best = (nums[left], nums[right])
        if total == target:
            break                      # can't get closer than exact
        if total < target:
            left += 1
        else:
            right -= 1
    return best

print(closest_pair([2, 5, 7, 9, 12, 16, 21], 31), closest_pair([1, 4, 10], 100))
# (9, 21) (4, 10)

Intermediate: two shapes and one argument

Opposite ends, or the same direction

Every two-pointer algorithm in this section has one of two shapes.

Opposite ends. One pointer starts at each end and they walk toward each other until they meet. Each step shrinks the range between them by one, so the loop runs at most n − 1 times. You use it when the decision depends on both ends at once: pair sums, palindromes, the water container below.

Same direction, often called reader and writer or slow and fast. Both start at the front. The reader looks at every item exactly once; the writer only moves when the reader finds something worth keeping. Everything before the writer is the finished answer. You use it to filter, compact or deduplicate a list in place.

There’s a third shape, pointers moving at different speeds through a linked list, and it gets its own part of Advanced.

Reader and writer: remove duplicates in place

Given a sorted list, keep one copy of each value at the front, without a second list, and return how many distinct values there are. Because the list is sorted, duplicates sit next to each other, so a value is new exactly when it differs from the last one you kept.

def remove_duplicates(nums):
    """nums is sorted. Keep one of each value at the front, in place; return how many."""
    if not nums:
        return 0
    write = 1                              # nums[:write] holds the distinct values seen so far
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:  # a value we haven't kept yet
            nums[write] = nums[read]
            write += 1
    return write

nums = [1, 1, 2, 3, 3, 3, 7, 9, 9]
k = remove_duplicates(nums)
print(k, nums[:k], nums)
# 5 [1, 2, 3, 7, 9] [1, 2, 3, 7, 9, 3, 7, 9, 9]

Look at the last print: everything after position 5 is leftover junk. That’s normal for in-place algorithms. The answer is nums[:k], and the caller is expected to ignore or truncate the rest. Python’s del nums[k:] does that.

The comment on write is the most important line in the function. It says what is true about the list every time the loop comes round: the first write slots hold the distinct values among everything read so far, in order. Hold on to that idea; it’s the subject of the section after next.

Move zeroes

Push every 0 to the end of a list and keep the other values in their original order, in place. Same shape: the reader scans, the writer marks where the next non-zero belongs.

def move_zeroes(nums):
    """Push every 0 to the end, keeping the other values in their order. In place."""
    write = 0                              # nums[:write] holds the non-zeros, in order
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

print(move_zeroes([0, 4, 0, 0, 7, 1, 0, 3]))
print(move_zeroes([5, 6]), move_zeroes([0, 0]))
# [4, 7, 1, 3, 0, 0, 0, 0]
# [5, 6] [0, 0]

Swapping instead of copying is what drags the zeros to the back: each swap moves a non-zero forward into the writer’s slot and moves whatever was there (a zero, or the same value when nothing has been skipped yet) to the reader’s slot. This is also, almost line for line, the partition step of quicksort that you’ll meet in Advanced, with “is not zero” replaced by “is less than the pivot”.

Container with most water

You get a list of wall heights. Pick two walls; the water they hold is the distance between them times the height of the shorter wall. Find the most water any pair can hold. For [1, 8, 6, 2, 5, 4, 8, 3, 7] the answer is 49: the walls of height 8 (index 1) and 7 (index 8), 7 apart, 7 high.

Checking all pairs is O(n²). The two-pointer answer starts with the widest container, the two outer walls, and then moves the shorter wall inward:

def max_area(heights):
    left, right = 0, len(heights) - 1
    best = 0
    while left < right:
        width = right - left
        area = width * min(heights[left], heights[right])
        best = max(best, area)
        if heights[left] < heights[right]:
            left += 1                      # the shorter wall limits every narrower container it's in
        else:
            right -= 1
    return best

print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))
print(max_area([1, 1]), max_area([4, 3, 2, 1, 4]))
# 49
# 1 16

Why the shorter one? Suppose the left wall is shorter. Every container that still uses it, with any right wall closer than the current one, is narrower than the one you just measured, and its height is still capped by that same short wall. Narrower and no taller means less water. So the short wall has nothing left to offer and can go. Moving the taller wall instead could only make things worse: the width shrinks and the short wall still caps the height.

Switch the demo above to Container with most water to watch the argument play out, including what happens when both walls are the same height.

3Sum: sort, then fix one and squeeze

Find every distinct triple in a list that sums to zero. [-1, 0, 1, 2, -1, -4] gives (-1, -1, 2) and (-1, 0, 1).

Brute force tries every triple, O(n³). The standard answer sorts once, then fixes the first number of the triple and runs pair sum on the rest of the list with the target set to minus that number. One O(n) squeeze for each of n first numbers is O(n²) overall, and the O(n log n) sort disappears inside that.

def three_sum(nums):
    nums = sorted(nums)
    triples = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue                        # same first value: same triples again
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                triples.append((nums[i], nums[left], nums[right]))
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1               # skip repeats of the middle value
    return triples

print(three_sum([-1, 0, 1, 2, -1, -4]))
print(three_sum([0, 0, 0, 0]), three_sum([1, 2, 3]))
# [(-1, -1, 2), (-1, 0, 1)]
# [(0, 0, 0)] []

The two skip branches are where most bugs live. Without them, [0, 0, 0, 0] reports (0, 0, 0) three times. Sorting is what makes deduplication cheap here: equal values are neighbors, so “same as the one before” is one comparison.

How much does it matter? On 400 random integers I timed a brute force over every combination against the version above (laptop, Python 3.13). Both found the same 2,674 triples. The brute force took 958 ms; sort plus two pointers took 10 ms. At 4,000 numbers the brute force would be roughly a thousand times slower again, and the two-pointer version about a hundred.

The pattern generalizes: kSum fixes k − 2 numbers with nested loops and squeezes the last two, for O(n^(k−1)) time.

Merging two sorted lists

The last classic is the one that matters most outside interviews. Given two sorted lists, produce one sorted list containing everything. Put a pointer at the front of each, take the smaller of the two front values, and advance that pointer.

def merge(a, b):
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:                    # <= keeps it stable: ties take from a first
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    out.extend(a[i:])                       # one side ran out: the rest of the other is already in order
    out.extend(b[j:])
    return out

print(merge([1, 4, 9, 12], [2, 3, 10, 15, 20]))
print(merge([], [1, 2]), merge([5], []))
# [1, 2, 3, 4, 9, 10, 12, 15, 20]
# [1, 2] [5]

Each comparison emits one value and advances one pointer, so merging lists of length m and n takes at most m + n − 1 comparisons: O(m + n). The <= matters more than it looks. It makes the merge stable: when values tie, the one from a comes first, so items that compare equal keep their original relative order. Merge sort, Python’s own sort and every database merge depend on that.

This loop is the heart of the Expert section. Keep it in mind.

Why discarding a side is safe: the loop invariant

“Move the smaller one” sounds like a heuristic. It isn’t, and the way to see that is to write down a loop invariant: a statement that is true before the loop starts and stays true after every pass. If the invariant plus “the loop has stopped” adds up to “the answer is correct”, you have a proof.

For pair sum on sorted nums, the invariant is:

If any pair sums to the target, there is one with both indices inside left..right.

Check it holds at each stage:

1. At the start, left..right is the whole list, so it’s trivially true.
2. When the sum is too small, nums[left] + nums[right] is below the target. For any j in range, nums[j] is at most nums[right] (the list is sorted), so nums[left] + nums[j] is also below the target. No answer uses index left with anything still in range. Removing left keeps the invariant true.
3. When the sum is too big, the mirror argument removes right.
4. When the loop stops without finding anything, left..right holds fewer than two indices, so it contains no pair, and by the invariant, no pair anywhere sums to the target.

There’s a second thing to prove: that the loop stops. Every pass shrinks right - left by exactly one, and it starts at n − 1, so there are at most n − 1 passes. A quantity like that, one that strictly decreases and can’t go below zero, is called a variant. Invariant for correctness, variant for termination: that pair is how you prove any loop.

There’s a lovely picture of the same argument. Lay out every pair as a cell in a grid, left value down the side, right value across the top. The two pointers stand on one cell. A “too small” step rules out the whole rest of the left pointer’s row; a “too big” step rules out the whole rest of the right pointer’s column.

The container problem has the same structure with a different invariant: the best container we haven’t measured yet uses two walls inside left..right, or we’ve already recorded something at least as good. Discarding the shorter wall keeps it true, for the reason in the previous section.

Proofs can still have mistakes in them, so I like to back them with a brute-force check on lots of small random inputs. This runs both problems against all-pairs answers:

import random
from itertools import combinations

def pair_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return True
        if total < target:
            left += 1
        else:
            right -= 1
    return False

def max_area(h):
    left, right, best = 0, len(h) - 1, 0
    while left < right:
        best = max(best, (right - left) * min(h[left], h[right]))
        if h[left] < h[right]:
            left += 1
        else:
            right -= 1
    return best

random.seed(1)
for trial in range(20_000):
    n = random.randint(0, 12)
    nums = sorted(random.randint(-20, 20) for _ in range(n))
    target = random.randint(-40, 40)
    brute = any(a + b == target for a, b in combinations(nums, 2))
    assert pair_sum(nums, target) == brute, (nums, target)
    h = [random.randint(0, 15) for _ in range(n)]
    brute_area = max([(j - i) * min(h[i], h[j]) for i, j in combinations(range(n), 2)], default=0)
    assert max_area(h) == brute_area, h
print("20,000 random cases: two pointers agrees with brute force")
# 20,000 random cases: two pointers agrees with brute force

Small inputs with small values are where the edge cases hide: empty lists, one item, all equal, negative numbers, a target nothing can reach. Twenty thousand of them run in a fifth of a second on my laptop.

What it costs

def sorted_squares(nums):
    out = [0] * len(nums)
    left, right = 0, len(nums) - 1
    for write in range(len(nums) - 1, -1, -1):   # fill from the back: biggest square first
        if abs(nums[left]) > abs(nums[right]):
            out[write] = nums[left] ** 2
            left += 1
        else:
            out[write] = nums[right] ** 2
            right -= 1
    return out

print(sorted_squares([-7, -3, -1, 0, 2, 5]))
print(sorted_squares([-4, -2]), sorted_squares([]))
# [0, 1, 4, 9, 25, 49]
# [4, 16] []

def merge_into(a, m, b):
    """a has m real values followed by len(b) spare slots. Merge b into a, in place."""
    i, j = m - 1, len(b) - 1
    for write in range(m + len(b) - 1, -1, -1):
        if j < 0:
            break                                  # b is used up; a's leftovers are already in place
        if i >= 0 and a[i] > b[j]:
            a[write] = a[i]; i -= 1
        else:
            a[write] = b[j]; j -= 1
    return a

print(merge_into([1, 4, 9, 0, 0, 0], 3, [2, 5, 12]))
print(merge_into([0, 0], 0, [3, 8]), merge_into([2, 7], 2, []))
# [1, 2, 4, 5, 9, 12]
# [3, 8] [2, 7]

def count_pairs_below(nums, target):
    """nums sorted. How many pairs i < j have nums[i] + nums[j] < target?"""
    left, right = 0, len(nums) - 1
    count = 0
    while left < right:
        if nums[left] + nums[right] < target:
            count += right - left                  # nums[left] pairs with every index in (left, right]
            left += 1
        else:
            right -= 1
    return count

from itertools import combinations
nums = [1, 2, 3, 5, 8, 13]
print(count_pairs_below(nums, 10), sum(a + b < 10 for a, b in combinations(nums, 2)))
# 7 7

Advanced: different speeds, and partitions in place

Linked lists: pointers you can only follow

A linked list stores each item in a node that holds a value and a reference to the next node. There are no indexes; to reach the fifth node, you start at the first (the head) and follow next four times. That changes the game for two pointers. You can’t jump to the end, and you can’t walk backwards. What you can do is move two pointers forward at different speeds.

class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, next=None):
        self.value, self.next = value, next

Normally the last node’s next is None. A bug, a corrupted structure or a badly built chain of references can instead point it back at an earlier node, making a cycle: following next then goes round forever. Detecting that is the most famous fast-and-slow problem.

Floyd’s cycle detection: the tortoise and the hare

Put two pointers at the head. Each step, the tortoise moves one node and the hare moves two. If the list ends, the hare reaches the end first and you’re done: no cycle. If there’s a cycle, both pointers eventually enter it, and inside a loop the faster one must catch up with the slower one from behind.

Why must it land on the tortoise rather than jump over it? Once both are in the loop, measure the gap from hare to tortoise going forward. Each step the tortoise adds one to it and the hare takes two away, so the gap shrinks by exactly one. A number that decreases by one each step can’t skip zero. So they meet, and they meet within one lap of the tortoise entering the loop.

The algorithm is usually credited to Robert W. Floyd; Donald Knuth attributes it to him in The Art of Computer Programming, Volume 2, although it doesn’t appear in Floyd’s published papers. Here it is:

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # one step
        fast = fast.next.next       # two steps
        if slow is fast:            # same node object, not just equal values
            return True
    return False                    # the hare fell off the end: no loop

Note the is. Two different nodes can hold the same value; what matters is whether the pointers refer to the same node.

Finding where the cycle starts

Knowing there’s a loop is half the job. Usually you want to know where it begins: which node is the first one you visit twice. Floyd’s algorithm has a second phase that finds it with no extra memory. After the pointers meet, move one of them back to the head. Then step both at speed one. The node where they meet again is the start of the cycle.

It looks like magic until you write down the distances. Call the tail length μ (the number of steps from the head to the loop’s entry), the loop length λ, and say the pointers met k steps past the entry.

The tortoise has walked μ + k nodes. The hare, at double speed, has walked 2(μ + k). They’re on the same node, so the hare’s extra distance, μ + k, must be a whole number of laps: μ + k = mλ for some whole number m. Rearranged, μ = mλ − k.

Now look at what phase 2 does. The pointer at the head needs μ steps to reach the entry. The pointer at the meeting point, after μ = mλ − k steps, has gone λ − k steps to complete its current lap (which lands on the entry) and then m − 1 more full laps (which land on the entry again). Both arrive at the entry at the same moment.

class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, next=None):
        self.value, self.next = value, next

def build(values, cycle_to=None):
    """Linked list of values; if cycle_to is an index, the last node points back to it."""
    nodes = [Node(v) for v in values]
    for a, b in zip(nodes, nodes[1:]):
        a.next = b
    if cycle_to is not None:
        nodes[-1].next = nodes[cycle_to]
    return nodes[0] if nodes else None

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # one step
        fast = fast.next.next       # two steps
        if slow is fast:            # same node object, not just equal values
            return True
    return False                    # the hare fell off the end: no loop

def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            break
    else:
        return None
    slow = head                     # phase 2: one pointer back to the start
    while slow is not fast:
        slow, fast = slow.next, fast.next   # both at speed one now
    return slow

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow                     # when the hare finishes, the tortoise is halfway

print(has_cycle(build([1, 2, 3, 4, 5])), has_cycle(build([1, 2, 3, 4, 5], cycle_to=2)))
print(cycle_start(build("ABCDEFGH", cycle_to=3)).value)
print(middle(build([1, 2, 3, 4, 5])).value, middle(build([1, 2, 3, 4, 5, 6])).value)

# Every tail length 0..30 and cycle length 1..30: does phase 2 always land on the entry?
for mu in range(31):
    for lam in range(1, 31):
        head = build(range(mu + lam), cycle_to=mu)
        assert cycle_start(head).value == mu
print("cycle start correct for all 930 shapes")
# False True
# D
# 3 4
# cycle start correct for all 930 shapes

The while ... else in cycle_start is a Python construct people rarely use: the else runs only when the loop ends without break, which here means “the hare fell off the end”. The exhaustive check at the bottom is the same habit as before. The algebra says it works; 930 shapes say I typed it correctly.

Finding the middle

middle in the code above is the other everyday use of fast and slow pointers. When the hare reaches the end, it has walked twice as far as the tortoise, so the tortoise is halfway. One pass, no counting the length first. On an even-length list this version returns the second of the two middle nodes (4 of 1 to 6); stop the hare one node earlier if you want the first. Merge sort on a linked list uses this to split the list in half, and the second Advanced exercise uses it to check a linked-list palindrome in O(1) space.

Floyd versus a visited set

The obvious way to detect a cycle is to remember every node you’ve seen in a set and stop at the first repeat. It’s simple, and it also tells you the cycle’s start directly. It costs memory proportional to the list. I measured both on a million-node list whose last node points back to node 300,000 (Python 3.13, laptop):

import time, tracemalloc

class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, next=None):
        self.value, self.next = value, next

def has_cycle_set(head):
    seen = set()
    node = head
    while node:
        if id(node) in seen:
            return True
        seen.add(id(node))
        node = node.next
    return False

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False

nodes = [Node(i) for i in range(1_000_000)]
for a, b in zip(nodes, nodes[1:]):
    a.next = b
nodes[-1].next = nodes[300_000]           # a long tail and a long loop
head = nodes[0]

for label, fn in (("visited set", has_cycle_set), ("Floyd", has_cycle)):
    start = time.perf_counter()
    fn(head)
    seconds = time.perf_counter() - start
    tracemalloc.start()
    fn(head)
    peak = tracemalloc.get_traced_memory()[1]
    tracemalloc.stop()
    print(f"{label:<12} {seconds * 1000:4.0f} ms  {peak / 2**20:5.1f} MiB extra")
# visited set   209 ms   67.2 MiB extra
# Floyd          26 ms    0.0 MiB extra

Floyd is eight times faster here and uses no memory at all. The set version pays for hashing a million IDs and growing a table to hold them. In C or Rust the speed gap narrows, but the memory gap doesn’t: constant versus linear.

When is the set still right? When the “list” is really a graph and nodes can have several successors, Floyd doesn’t apply, and you need a visited set (that’s depth-first search). Floyd works when every node has exactly one next, which mathematicians call a functional graph: a function applied over and over. That’s more common than linked lists suggest. Pollard’s rho algorithm for factoring integers runs Floyd’s method on the sequence x, f(x), f(f(x)), … and the first Advanced exercise below treats an array as one.

Partitioning: the Dutch national flag

Partitioning means rearranging an array so that everything smaller than some value, the pivot, comes first and everything larger comes after. Edsger Dijkstra posed the three-color version as the Dutch national flag problem: given a row of red, white and blue items, put all the reds first, then the whites, then the blues, in one pass, using only swaps.

It takes three pointers. low marks the end of the “less than” region, high marks the start of the “greater than” region at the back, and mid scans the unknown middle.

def dutch_flag(items, pivot):
    """Rearrange in place into  < pivot | == pivot | > pivot.  One pass, O(1) extra space."""
    low, mid, high = 0, 0, len(items) - 1
    while mid <= high:
        if items[mid] < pivot:
            items[low], items[mid] = items[mid], items[low]
            low += 1
            mid += 1
        elif items[mid] > pivot:
            items[mid], items[high] = items[high], items[mid]
            high -= 1                  # don't move mid: the value swapped in is unexamined
        else:
            mid += 1
    return items

print(dutch_flag([2, 0, 2, 1, 1, 0, 0, 2, 1], 1))
print(dutch_flag([5, 1, 9, 5, 3, 7, 5], 5))
# [0, 0, 0, 1, 1, 1, 2, 2, 2]
# [1, 3, 5, 5, 5, 7, 9]

The asymmetry is the bug magnet. After swapping with low, you can advance mid, because the value that comes back from low was already examined (it’s an “equal” value, or low and mid are the same slot). After swapping with high, you must not advance mid: the value that arrived from the back hasn’t been looked at yet. The invariant makes that obvious, which is the point of having one: items[:low] is less, items[low:mid] is equal, items[mid:high + 1] is unknown, items[high + 1:] is greater. The loop ends when the unknown region is empty. Its variant, high - mid, shrinks by one on every pass.

Note the loop condition is mid <= high, not mid < high. The unknown region is mid..high inclusive, so a single unknown item still needs a look. That’s the < versus <= decision from Beginner, and here getting it wrong leaves one item unsorted.

Quicksort’s partition: Lomuto and Hoare

Quicksort is “partition around a pivot, then sort each side”. The partition step comes in two classic versions, and they are the two two-pointer shapes you already know.

Lomuto’s partition is reader and writer: one pointer scans, another marks the end of the “less than pivot” region, exactly like move zeroes. Hoare’s partition, from Tony Hoare’s original 1961 quicksort, is opposite ends: one pointer walks right looking for a value that belongs on the right, the other walks left looking for one that belongs on the left, and when both have found one, they swap.

I counted comparisons and swaps for both inside the same quicksort (laptop, Python 3.13):

import random

def lomuto(a, lo, hi, stats):
    pivot = a[hi]
    store = lo                          # a[lo:store] < pivot
    for scan in range(lo, hi):
        stats["compares"] += 1
        if a[scan] < pivot:
            a[store], a[scan] = a[scan], a[store]
            stats["swaps"] += 1
            store += 1
    a[store], a[hi] = a[hi], a[store]
    stats["swaps"] += 1
    return store

def hoare(a, lo, hi, stats):
    pivot = a[(lo + hi) // 2]
    i, j = lo - 1, hi + 1
    while True:
        i += 1
        stats["compares"] += 1
        while a[i] < pivot:
            i += 1; stats["compares"] += 1
        j -= 1
        stats["compares"] += 1
        while a[j] > pivot:
            j -= 1; stats["compares"] += 1
        if i >= j:
            return j
        a[i], a[j] = a[j], a[i]
        stats["swaps"] += 1

def quicksort(a, scheme):
    stats = {"compares": 0, "swaps": 0}
    stack = [(0, len(a) - 1)]
    while stack:
        lo, hi = stack.pop()
        if lo >= hi:
            continue
        if scheme == "lomuto":
            p = lomuto(a, lo, hi, stats)
            stack += [(lo, p - 1), (p + 1, hi)]
        else:
            p = hoare(a, lo, hi, stats)
            stack += [(lo, p), (p + 1, hi)]
    return stats

random.seed(3)
data = [random.random() for _ in range(100_000)]
for scheme in ("lomuto", "hoare"):
    a = data[:]
    s = quicksort(a, scheme)
    assert a == sorted(data)
    print(f"random  {scheme:<6} compares {s['compares']:>10,}  swaps {s['swaps']:>9,}")

same = [7] * 5_000
for scheme in ("lomuto", "hoare"):
    a = same[:]
    s = quicksort(a, scheme)
    print(f"equal   {scheme:<6} compares {s['compares']:>10,}  swaps {s['swaps']:>9,}")
# random  lomuto compares  2,032,046  swaps 1,091,906
# random  hoare  compares  2,434,447  swaps   383,033
# equal   lomuto compares 12,497,500  swaps     4,999
# equal   hoare  compares     69,606  swaps    29,804

Two results worth remembering. On random data, Hoare does about a third of Lomuto’s swaps, because it only swaps values that are both on the wrong side, while Lomuto swaps every small value it meets. And on an array where every value is equal, Lomuto collapses: each partition puts everything on one side, the recursion goes n levels deep, and 5,000 equal values cost 12.5 million comparisons, which is n²/2. Hoare’s pointers stop on equal values from both sides and swap them, which splits the array evenly, so it stays fast. A three-way partition (the Dutch flag) is even better on data with many repeats: the “equal” block is finished and never touched again.

That isn’t an exotic case. Sorting a million rows by a status column with four distinct values is mostly equal keys. Production sorts care: Go’s sort package has used pattern-defeating quicksort (pdqsort, by Orson Peters) since Go 1.19, and Rust’s sort_unstable was built on it. pdqsort notices runs of equal keys and partitions them out as a block, and falls back to heapsort if recursion gets too deep.

In place means O(1) space, and what that costs you

Most of the algorithms in this article are in place: they use O(1) extra space, a few index variables, and rearrange the input instead of building a new one. That’s valuable when the data is large, on small devices, and inside libraries where an allocation per call would hurt.

It has three costs, and tutorials rarely mention them:

1. You destroy the input. remove_duplicates leaves junk after position k, and the original order is gone after a partition. If a caller still needs the original, you’ve just made them copy it, and the space saving is gone.
2. In-place partitions aren’t stable. Hoare’s partition and the Dutch flag reorder equal elements. If you’re partitioning orders by status and expect orders within each status to stay in date order, they won’t. Stable partitioning in place is possible but slower; usually the honest answer is to use extra memory.
3. It’s harder to read and easier to get wrong. Every bug in this article so far (< versus <=, advancing mid after the wrong swap, overwriting unread values) is an in-place bug. An out-of-place version [x for x in nums if x != 0] + [0] * zeros has none of them.

My default in application code is the clear out-of-place version, and in place when a measurement says memory matters.

The cost of sorting first

Opposite-end pointers need sorted input, and sorting isn’t free. Comparison sorting n items needs O(n log n) comparisons in the worst case, which for a million items is about 20 million, against a million for one pass. Here’s what that looks like in Python (best of three, laptop):

import random, time

random.seed(5)
n = 1_000_000
shuffled = [random.random() for _ in range(n)]
already = sorted(shuffled)
backwards = already[::-1]

def ms(fn):
    best = float("inf")
    for _ in range(3):
        start = time.perf_counter()
        fn()
        best = min(best, time.perf_counter() - start)
    return best * 1000

print(f"one pass, sum():         {ms(lambda: sum(shuffled)):6.1f} ms")
print(f"sorted(), random order:  {ms(lambda: sorted(shuffled)):6.1f} ms")
print(f"sorted(), already sorted:{ms(lambda: sorted(already)):6.1f} ms")
print(f"sorted(), reversed:      {ms(lambda: sorted(backwards)):6.1f} ms")
# one pass, sum():            2.5 ms
# sorted(), random order:   141.5 ms
# sorted(), already sorted:  16.5 ms
# sorted(), reversed:        18.6 ms

Sorting a million random floats costs about 57 times a simple pass. But look at the last two lines. Python’s sort (Timsort, and Powersort’s merge policy since 3.11) scans for runs that are already in order, ascending or descending, reverses the descending ones with that reverse_slice loop, and merges runs with the two-pointer merge from Intermediate. On data that’s already sorted, it’s one pass of comparisons, which is why it took 16.5 ms instead of 141.5.

The practical lesson: sorting first is cheap when the data is nearly sorted, and very often it already is. Rows read by an indexed ORDER BY, log lines in time order, files from a sorted listing, IDs that were generated in sequence. When the data arrives sorted, two pointers is free money. When it doesn’t, a hash map usually wins, unless you need what only order gives you.

A ring buffer: two pointers chasing in a circle

One more in-place structure, because it shows up everywhere data flows between a producer and a consumer. A ring buffer is a fixed-size array used as a queue. The writer adds at one pointer, the reader takes from another, and both wrap around to the start when they reach the end. Nothing is ever shifted, and nothing is allocated after creation.

class RingBuffer:
    """A fixed-size queue: the writer chases the reader around one array."""

    def __init__(self, capacity):
        self.slots = [None] * capacity
        self.read = 0        # next slot to read; only the consumer moves it
        self.write = 0       # next slot to write; only the producer moves it
        self.count = 0

    def push(self, item):
        if self.count == len(self.slots):
            return False                                   # full: the writer has lapped the reader
        self.slots[self.write] = item
        self.write = (self.write + 1) % len(self.slots)    # wrap around instead of growing
        self.count += 1
        return True

    def pop(self):
        if self.count == 0:
            return None                                    # empty: the reader caught the writer
        item, self.slots[self.read] = self.slots[self.read], None
        self.read = (self.read + 1) % len(self.slots)
        self.count -= 1
        return item

q = RingBuffer(3)
print([q.push(x) for x in "abcd"])
print(q.pop(), q.pop(), q.push("e"), q.push("f"))
print([q.pop() for _ in range(4)], q.read, q.write)
# [True, True, True, False]
# a b True True
# ['c', 'e', 'f', None] 2 2

The fourth push fails: the buffer is full and refuses rather than growing. That refusal is the whole point in a real system. A bounded queue that says no is how a fast producer learns to slow down. Notice also that the pointers are equal both when the buffer is empty and when it’s full, which is why this version keeps a count. (The other common fix is to leave one slot always empty.)

def find_duplicate(nums):
    """nums has n + 1 values, each in 1..n. Return the repeated one without changing nums."""
    slow = fast = nums[0]
    while True:
        slow = nums[slow]               # treat i -> nums[i] as a 'next' pointer
        fast = nums[nums[fast]]
        if slow == fast:
            break
    slow = nums[0]
    while slow != fast:
        slow, fast = nums[slow], nums[fast]
    return slow                         # the cycle's entry is the value two indices point to

print(find_duplicate([1, 3, 4, 2, 2]), find_duplicate([3, 1, 3, 4, 2]), find_duplicate([2, 2, 2, 2]))

import random
random.seed(11)
for _ in range(2000):
    n = random.randint(1, 50)
    dup = random.randint(1, n)
    nums = list(range(1, n + 1)) + [dup]
    random.shuffle(nums)
    assert find_duplicate(nums) == dup
print("2,000 random cases ok")
# 2 3 2
# 2,000 random cases ok

class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, next=None):
        self.value, self.next = value, next

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def is_palindrome_list(head):
    slow = fast = head
    while fast and fast.next:           # find the middle
        slow, fast = slow.next, fast.next.next
    prev = None
    while slow:                         # reverse the second half in place
        slow.next, prev, slow = prev, slow, slow.next
    left, right = head, prev
    while right:                        # walk inward from both ends
        if left.value != right.value:
            return False
        left, right = left.next, right.next
    return True

for values in ([1, 2, 3, 2, 1], [1, 2, 2, 1], [1, 2, 3], [7], []):
    print(values, is_palindrome_list(build(values)))
# [1, 2, 3, 2, 1] True
# [1, 2, 2, 1] True
# [1, 2, 3] False
# [7] True
# [] True

Expert: the merge step everywhere

At this level the question stops being “how do I solve this problem with two pointers” and becomes “where is the merge step already running, and what breaks it”. The answer is: inside your database, inside your sort, inside your sync jobs, and wherever two ordered streams have to be compared.

How PostgreSQL’s merge join works

A join combines rows from two tables that match on some column, like customers and their orders on customer_id. PostgreSQL has three ways to execute one. Its documentation describes the merge join like this:

Each relation is sorted on the join attributes before the join starts. Then the two relations are scanned in parallel, and matching rows are combined to form join rows. This kind of join is attractive because each relation has to be scanned only once. The required sorting might be achieved either by an explicit sort step, or by scanning the relation in the proper order using an index on the join key.

“Scanned in parallel” is two pointers. The executor’s own source (src/backend/executor/nodeMergejoin.c) spells out the loop in its header comment:

Join {
    get initial outer and inner tuples              INITIALIZE
    do forever {
        while (outer != inner) {                    SKIP_TEST
            if (outer < inner)
                advance outer                       SKIPOUTER_ADVANCE
            else
                advance inner                       SKIPINNER_ADVANCE
        }
        mark inner position                         SKIP_TEST
        do forever {
            while (outer == inner) {
                join tuples                         JOINTUPLES
                advance inner position              NEXTINNER
            }
            advance outer position                  NEXTOUTER
            if (outer == mark)                      TESTOUTER
                restore inner position to mark      TESTOUTER
            else
                break  // return to top of outer loop
        }
    }
}

The skip loop is the merge from Intermediate: advance whichever side is behind. The new part is mark and restore. Keys can repeat on both sides. If the outer table has two rows with key 5 and the inner has four, all eight combinations must come out. So when the executor reaches the first inner 5, it marks that position, joins the first outer 5 with every inner 5, and then, when the next outer row is also 5, rewinds the inner pointer to the mark and does it again. In Python:

def merge_join(outer, inner, key=lambda row: row[0]):
    """Inner join of two lists already sorted by key. Handles repeated keys on both sides."""
    i = j = 0
    while i < len(outer) and j < len(inner):
        a, b = key(outer[i]), key(inner[j])
        if a < b:
            i += 1
        elif a > b:
            j += 1
        else:
            mark = j                                  # first inner row with this key
            while i < len(outer) and key(outer[i]) == a:
                j = mark                              # restore: rewind inner to the mark
                while j < len(inner) and key(inner[j]) == a:
                    yield outer[i], inner[j]
                    j += 1
                i += 1

customers = [(1, "Aisha"), (2, "Ben"), (4, "Chen"), (4, "Chen (old record)"), (7, "Dana")]
orders = [(1, "order 10"), (3, "order 11"), (4, "order 12"), (4, "order 13"), (7, "order 14")]
for pair in merge_join(customers, orders):
    print(pair)
# ((1, 'Aisha'), (1, 'order 10'))
# ((4, 'Chen'), (4, 'order 12'))
# ((4, 'Chen'), (4, 'order 13'))
# ((4, 'Chen (old record)'), (4, 'order 12'))
# ((4, 'Chen (old record)'), (4, 'order 13'))
# ((7, 'Dana'), (7, 'order 14'))

Rewinding means the inner side has to support going back, which is why PostgreSQL’s access methods provide “mark” and “restore” operations, and why the planner sometimes inserts a Materialize node to buffer an inner input that can’t rewind.

Watching the planner choose one

To see when the planner picks a merge join, I loaded a million customers and three million orders into a local PostgreSQL 14.13 on my laptop, with an index on both join columns:

CREATE TABLE customers (id int PRIMARY KEY, name text);
CREATE TABLE orders (id int PRIMARY KEY, customer_id int NOT NULL, total_cents int);
INSERT INTO customers SELECT g, 'customer ' || g FROM generate_series(1, 1000000) g;
INSERT INTO orders SELECT g, (g::bigint * 7919 % 1000000)::int + 1, g % 10000 FROM generate_series(1, 3000000) g;
CREATE INDEX orders_customer_id ON orders (customer_id);
VACUUM ANALYZE customers;
VACUUM ANALYZE orders;

Asked for the join with no particular order, the planner builds a hash table:

EXPLAIN (COSTS OFF) SELECT c.name, o.total_cents
FROM customers c JOIN orders o ON o.customer_id = c.id;

 Hash Join
   Hash Cond: (o.customer_id = c.id)
   ->  Seq Scan on orders o
   ->  Hash
         ->  Seq Scan on customers c

Add ORDER BY c.id and the plan changes completely:

EXPLAIN (COSTS OFF) SELECT c.name, o.total_cents
FROM customers c JOIN orders o ON o.customer_id = c.id ORDER BY c.id;

 Merge Join
   Merge Cond: (c.id = o.customer_id)
   ->  Index Scan using customers_pkey on customers c
   ->  Index Scan using orders_customer_id on orders o

Both indexes already hold their rows in key order, so walking them gives two sorted streams for free. A merge join over them produces output that’s already in c.id order, so there’s no sort step at all. The hash join would have to sort three million joined rows afterwards. That’s the planner reasoning in this article’s terms: if the data is already sorted, two pointers is free.

You can make it show you the alternative by turning merge joins off for one session (a diagnostic switch, never something to set in production):

SET enable_mergejoin = off;
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF) SELECT c.name, o.total_cents
FROM customers c JOIN orders o ON o.customer_id = c.id ORDER BY c.id;

 Gather Merge (actual rows=3000000 loops=1)
   Workers Planned: 2
   Workers Launched: 2
   ->  Sort (actual rows=1000000 loops=3)
         Sort Key: c.id
         Sort Method: external merge  Disk: 33528kB
         Worker 0:  Sort Method: external merge  Disk: 32592kB
         Worker 1:  Sort Method: external merge  Disk: 33760kB
         ->  Parallel Hash Join (actual rows=1000000 loops=3)
               Hash Cond: (o.customer_id = c.id)
               ->  Parallel Seq Scan on orders o (actual rows=1000000 loops=3)
               ->  Parallel Hash (actual rows=333333 loops=3)
                     Buckets: 65536  Batches: 16  Memory Usage: 4000kB
                     ->  Parallel Seq Scan on customers c (actual rows=333333 loops=3)

Two more two-pointer algorithms just appeared. Sort Method: external merge Disk: 33528kB means each worker’s sort didn’t fit in work_mem (4 MB by default) and spilled to disk as sorted runs, which were then merged. And Gather Merge combines the three workers’ sorted outputs into one sorted stream: a three-way merge. Across ten runs on my laptop, the merge join plan usually took 1.6 to 1.8 seconds and this one 2.3 to 3.7 seconds, with the odd slow outlier for both. The exact numbers mean little outside my machine; the shape of the plans is the lesson.

The planner doesn’t always pick the merge, and it isn’t always right. I built two 900,000-row tables keyed by a text SKU, both with primary-key indexes, and diffed them with a FULL JOIN (more on that query below). The planner chose a hash full join, whose hash table spilled into 16 batches at the default work_mem. Forcing a merge full join over the two indexes ran in 206 to 238 ms against 695 to 1,042 ms for the plan it chose. On my laptop, with everything cached, the index scans were cheap; the planner’s default cost settings assume disk reads that a cached laptop doesn’t do. The lesson is not “turn off hash joins”. It’s that the planner estimates, EXPLAIN ANALYZE measures, and when a join is slow you should check both.

External merge sort: sorting what doesn’t fit

The plan above sorted on disk. Here’s the idea, small enough to read. Cut the input into chunks that fit in memory, sort each chunk and write it out as a run, then merge all the runs with one pointer per run:

import heapq, itertools, os, random, tempfile

def external_sort(numbers, run_size):
    """Sort a stream bigger than memory: sort fixed-size runs, spill each to disk, then k-way merge."""
    paths = []
    numbers = iter(numbers)
    while run := list(itertools.islice(numbers, run_size)):
        run.sort()                                   # phase 1: an in-memory sort of one run
        fd, path = tempfile.mkstemp(suffix=".run")
        with os.fdopen(fd, "w") as f:
            f.writelines(f"{x}\n" for x in run)
        paths.append(path)
    files = [open(p) for p in paths]
    try:
        streams = [(int(line) for line in f) for f in files]
        yield from heapq.merge(*streams)             # phase 2: one pointer per run, smallest head wins
    finally:
        for f in files:
            f.close()
        for p in paths:
            os.remove(p)

random.seed(2)
data = [random.randrange(1_000_000) for _ in range(100_000)]
out = list(external_sort(data, run_size=10_000))
print(out == sorted(data), len(out), "values merged from", -(-len(data) // 10_000), "runs")
# True 100000 values merged from 10 runs

Memory holds one run at a time during phase 1, and only the current line of each file during phase 2. Each value is read from disk once and written once more. That’s the reason merge-based sorting dominates whenever data lives on disk or comes in streams: every input is read sequentially, front to back, which disks, networks and caches are all fastest at.

k-way merge: more than two pointers

With two runs you compare two heads. With k runs, comparing all k heads for every output value costs O(k) each, O(nk) total. A min-heap of the k heads brings that down to O(log k) per value: pop the smallest, push the next value from the run it came from. That’s what heapq.merge does, and it’s the same idea as PostgreSQL’s Gather Merge and the compaction step in LSM-tree databases such as RocksDB and Cassandra, which merge many sorted files into fewer.

Diffing two sorted sets in one pass

Here’s the pattern I’d most like every backend engineer to know. You have a source of truth and a replica: a product catalog and a search index, files on disk and objects in a bucket, users in your database and users in a mailing tool. You need to know three things: what’s only in the source (add it), what’s only in the replica (delete it), and what’s in both but different (update it).

If both sides can be read in key order, one merge pass answers all three:

def sorted_diff(source, replica):
    """Both iterables yield (key, version) sorted by key, keys unique per side.
    Yields ('add', key) / ('delete', key) / ('update', key) in one pass, O(1) memory."""
    END = object()
    src, dst = iter(source), iter(replica)
    a, b = next(src, END), next(dst, END)
    while a is not END or b is not END:
        if b is END or (a is not END and a[0] < b[0]):
            yield "add", a[0]                  # only in source
            a = next(src, END)
        elif a is END or b[0] < a[0]:
            yield "delete", b[0]               # only in replica
            b = next(dst, END)
        else:
            if a[1] != b[1]:
                yield "update", a[0]           # in both, but different
            a, b = next(src, END), next(dst, END)

source = [("a.html", 3), ("b.html", 1), ("d.css", 2), ("e.js", 5)]
replica = [("a.html", 3), ("c.png", 1), ("d.css", 1), ("e.js", 5), ("f.txt", 9)]
print(list(sorted_diff(source, replica)))
# [('add', 'b.html'), ('delete', 'c.png'), ('update', 'd.css'), ('delete', 'f.txt')]

The END sentinel lets the loop run until both sides are exhausted, so leftovers on either side are handled by the same two branches instead of separate cleanup loops. Everything is a generator: the function never holds more than one item from each side.

The hash-based alternative loads both sides into dictionaries and uses set operations. For data that fits in memory it’s perfectly fine, and simpler. To see the difference, I diffed two million-row listings (generated, 10% only-in-source, 10% only-in-replica, about 1% changed), read as generators (laptop, Python 3.13):

import time, tracemalloc

def set_diff(source, replica):
    src, dst = dict(source), dict(replica)
    adds = src.keys() - dst.keys()
    deletes = dst.keys() - src.keys()
    updates = {k for k in src.keys() & dst.keys() if src[k] != dst[k]}
    return len(adds) + len(deletes) + len(updates)

def gen_source(n):          # generators: neither side is ever held in memory
    for i in range(n):
        if i % 10 != 3:
            yield f"sku-{i:07d}", i % 500

def gen_replica(n):
    for i in range(n):
        if i % 10 != 7:
            yield f"sku-{i:07d}", (i % 500) + (i % 97 == 0)

N = 1_000_000
for label, run in (
    ("sorted diff over two generators", lambda: sum(1 for _ in sorted_diff(gen_source(N), gen_replica(N)))),
    ("dicts and set operations", lambda: set_diff(gen_source(N), gen_replica(N))),
):
    start = time.perf_counter()
    changes = run()
    seconds = time.perf_counter() - start
    tracemalloc.start()
    run()
    peak = tracemalloc.get_traced_memory()[1]
    tracemalloc.stop()
    print(f"{label:<32} {changes:,} changes  {seconds * 1000:5.0f} ms  peak {peak / 2**20:6.1f} MiB")
# sorted diff over two generators  208,248 changes    572 ms  peak    0.0 MiB
# dicts and set operations         208,248 changes   1440 ms  peak  230.6 MiB

(This block reuses sorted_diff from above.) Same answer. The merge took 40% of the time and essentially no memory; the dictionaries peaked at 230 MiB, and that number grows with the data. At ten million rows the dictionaries need gigabytes and the merge still needs nothing. In SQL, the same diff is a FULL OUTER JOIN on the key, filtered to rows where one side is missing or the versions differ, and with indexes on both keys PostgreSQL can run it as a merge full join.

The catch is the precondition: both sides must arrive sorted by the same key, in the same order. When they come from databases or object stores that list in key order, that’s free. When they don’t, you pay for a sort, or you fall back to the hash version.

The precondition that bites: both sides sorted the same way

“Sorted” isn’t one thing. It depends on the comparison. Python compares strings by code point, so "B" (66) sorts before "a" (97). A database column with a linguistic collation such as en_US compares letters first and treats case only as a tie-breaker, so "about" comes before "Blog". Feed one ordering of each into a merge and watch what happens to two identical sets:

def sorted_diff(source, replica):
    END = object()
    src, dst = iter(source), iter(replica)
    a, b = next(src, END), next(dst, END)
    while a is not END or b is not END:
        if b is END or (a is not END and a[0] < b[0]):
            yield "add", a[0]
            a = next(src, END)
        elif a is END or b[0] < a[0]:
            yield "delete", b[0]
            b = next(dst, END)
        else:
            if a[1] != b[1]:
                yield "update", a[0]
            a, b = next(src, END), next(dst, END)

files = [("about.html", 1), ("Blog.html", 1), ("cv.pdf", 1), ("index.html", 1)]

byte_order = sorted(files)                                    # 'B' (66) sorts before 'a' (97)
case_folded = sorted(files, key=lambda f: f[0].casefold())    # roughly what a linguistic collation does
print([f for f, _ in byte_order])
print([f for f, _ in case_folded])
print(list(sorted_diff(byte_order, case_folded)))             # identical sets, two different orders

def checked(rows):
    """Refuse to continue if the input isn't strictly increasing: a merge's precondition."""
    previous = None
    for row in rows:
        if previous is not None and not previous < row[0]:
            raise ValueError(f"input not sorted: {previous!r} then {row[0]!r}")
        previous = row[0]
        yield row

try:
    list(sorted_diff(checked(byte_order), checked(case_folded)))
except ValueError as e:
    print("ValueError:", e)
# ['Blog.html', 'about.html', 'cv.pdf', 'index.html']
# ['about.html', 'Blog.html', 'cv.pdf', 'index.html']
# [('add', 'Blog.html'), ('delete', 'Blog.html')]
# ValueError: input not sorted: 'about.html' then 'Blog.html'

Nothing differs between the two sides, yet the diff says “upload Blog.html, then delete Blog.html”. Run those actions in that order against a real bucket and a page disappears from your site, with no error anywhere. This is the most dangerous property of merge algorithms: an ordering mismatch doesn’t crash, it produces confident, wrong output. Hash-based diffs don’t have this failure mode, which is a real argument for them when the inputs come from different systems.

Two defenses, and I’d use both. First, make the ordering explicit at the source: in PostgreSQL, ORDER BY key COLLATE "C" sorts by bytes regardless of the database’s default collation, and in Python, sort by the same key function on both sides. Second, check the precondition as you stream, like checked above. It costs one comparison per item, and it turns silent corruption into a loud error. The checker uses the same comparison as the merge, which is the point: it validates the order the merge will actually assume.

Two pointers over streams

Everything in this section used generators, not lists, and that’s the real reason the merge step runs the world. Opposite-end pointers need random access to both ends. Same-direction pointers only ever move forward, which means they work on streams: rows from a cursor, lines from a file, pages from an API, messages from a queue. You never need to hold the data, only the current item from each side.

That changes what a “pointer” is. In a database cursor, a paginated API or a queue consumer, the pointer is a position you can save: the last key you processed. Save it, crash, restart, and you carry on from there. Two questions decide whether that’s safe, and they’re the same two questions as any loop invariant. What does the saved position promise about everything before it? And does the order have ties, so that “after this key” is ambiguous? You’ll see both answered in real code in the next section.

Concurrency adds a twist. In the ring buffer from Advanced, if only the producer ever writes write and only the consumer ever writes read, the two threads never write the same variable. Leslie Lamport showed in 1983 that a single-producer, single-consumer queue built this way needs no lock at all, provided each side publishes its pointer only after the slot is fully written (on modern hardware that takes memory-ordering barriers). That’s how many logging pipelines and audio buffers hand data between threads. It breaks immediately with two producers, because then two threads move the same pointer. In Python, use queue.Queue or collections.deque and let the library handle it.

Proving it: precondition, invariant, variant

Every algorithm here was justified the same way, and it’s worth naming the method because it scales to code no tutorial covers:

• Precondition: what must be true of the input. Sorted ascending by the same comparison on both sides. Check it when the input crosses a trust boundary.
• Invariant: what each pass preserves. No answer lies outside left..right. items[:low] is less than the pivot. Everything before the cursor has been processed.
• Variant: a number that strictly decreases and can’t go below zero. right - left. high - mid. Items left unread. It proves the loop ends.
• Postcondition: what invariant plus exit condition give you. The range is empty, so no pair exists.

You can put the reasoning into the code as assertions while you develop:

def pair_sum_checked(nums, target):
    assert all(x <= y for x, y in zip(nums, nums[1:])), "precondition: sorted"
    left, right = 0, len(nums) - 1
    while left < right:
        # Invariant: no pair using an index outside [left, right] sums to target.
        total = nums[left] + nums[right]
        if total == target:
            return left, right
        width = right - left                    # variant: shrinks by exactly 1 per step
        if total < target:
            left += 1
        else:
            right -= 1
        assert right - left == width - 1
    return None                                 # [left, right] holds < 2 indices: no pair is left

print(pair_sum_checked([2, 5, 7, 9, 12, 16, 21], 25), pair_sum_checked([1, 2], 9))
# (3, 5) None

The precondition check is O(n), the same cost as the whole algorithm, so in a hot path you’d drop it; at a system boundary, where data from somewhere else meets an algorithm that silently assumes order, keep it.

One research-grade footnote for cycle detection. Floyd isn’t the fastest option. Brent’s algorithm (Richard Brent, 1980) keeps the tortoise still and teleports it to the hare’s position whenever the hare has run a power of two steps; it finds the loop length directly and, in Brent’s analysis, uses noticeably fewer function evaluations than Floyd on average. When each step is expensive, as in Pollard’s rho factoring, that matters. For linked lists in application code, Floyd is simpler and fast enough.

In a design review

When a design contains “compare these two collections” or “process this stream in order”, these are the questions I ask:

1. Do both sides arrive sorted, and by exactly the same comparison? Name the collation, the case rules and how ties break. If not, who sorts, and at what cost?
2. Does the data fit in memory, now and in a year? If yes, a hash diff is simpler and has no ordering trap. If no, the merge is the only one-pass option.
3. Is the key unique on each side? If not, the merge needs mark and restore (a join), not a diff.
4. Where is the pointer saved, and what does it promise? For a stream that can crash halfway, the saved position is the invariant made durable.
5. What happens on a precondition violation? Silent wrong output, or a loud stop?

def common_to_all(*streams):
    """Each stream yields strictly increasing values. Yield the values every stream contains."""
    END = object()
    its = [iter(s) for s in streams]
    heads = [next(it, END) for it in its]
    while END not in heads:
        high = max(heads)
        if all(h == high for h in heads):
            yield high
            heads = [next(it, END) for it in its]       # everyone advances past the match
        else:
            for k, it in enumerate(its):
                while heads[k] is not END and heads[k] < high:
                    heads[k] = next(it, END)             # anyone behind catches up to the leader

print(list(common_to_all([1, 3, 4, 7, 9, 12], [2, 3, 7, 8, 12], [3, 5, 7, 12, 40])))
print(list(common_to_all(range(0, 10**6, 6), range(0, 10**6, 10), range(0, 10**6, 15)))[:5])
print(list(common_to_all([1, 2], [])))
# [3, 7, 12]
# [0, 30, 60, 90, 120]
# []

def merge_join_buggy(outer, inner):
    i = j = 0
    while i < len(outer) and j < len(inner):
        if outer[i][0] < inner[j][0]:
            i += 1
        elif outer[i][0] > inner[j][0]:
            j += 1
        else:
            yield outer[i], inner[j]
            i += 1
            j += 1

def merge_join_buggy(outer, inner):
    i = j = 0
    while i < len(outer) and j < len(inner):
        if outer[i][0] < inner[j][0]:
            i += 1
        elif outer[i][0] > inner[j][0]:
            j += 1
        else:
            yield outer[i], inner[j]
            i += 1
            j += 1

customers = [(4, "Chen"), (4, "Chen (old record)")]
orders = [(4, "order 12"), (4, "order 13")]
print(list(merge_join_buggy(customers, orders)))
# [((4, 'Chen'), (4, 'order 12')), ((4, 'Chen (old record)'), (4, 'order 13'))]

In production: where the pattern actually runs

I’m the primary engineer of ezychat.io, a multi-tenant platform where AI and people answer customers on WhatsApp, Instagram, Messenger and web chat. It’s Python (FastAPI and Celery) on PostgreSQL and Redis. Before writing this section I searched the backend for two-pointer code: index loops walking inward, merges of sorted lists, heapq.merge, sorted diffs. I’ll be straight about what I found. I found no hand-written opposite-ends loop in it, and no hand-written merge. The interview-style patterns don’t appear, and I think that’s the right outcome, for reasons worth spelling out. What does appear is the same-direction pattern, as a saved pointer over an ordered stream, and the merge step running underneath, in PostgreSQL and in this site’s own deploy.

Where ezychat diffs with hash maps instead

Several places in ezychat compare two collections, and every one of them uses sets or dictionaries. One example is reconciling a WhatsApp group’s members with the deal room’s records: Meta returns the current member list, and the room’s participant records have to agree with it. Trimmed from dealrooms/cloud.py:

async def _settle_roster(
    session: AsyncSession, room: DealRoom, members: list[dict]
) -> tuple[int, int]:
    """Make the room's records agree with the members Meta lists, as of now:
    somebody listed is in, somebody the room had in and Meta does not list
    has left. Records only — nothing here removes anybody from WhatsApp."""
    ...
    present_ids = {person.id for person in present}
    ...
    for person in await ladder.room_participants(session, room):
        if person.membership_state == "joined" and person.id not in present_ids:
            person.membership_state = "left"
            ...

That’s the sorted diff’s “only in replica” branch, done with a set. And it’s right. The member list comes from an API in no promised order, it’s small, and the code has to resolve each member to a participant record anyway. Sorting both sides to save a set of a few dozen IDs would add an ordering precondition (the trap from Expert) and buy nothing. The catalog import’s compute_diff in catalog/service.py makes the same choice for product units, indexing both sides by unit.name.casefold() in dictionaries, and its docstring is about the cost that actually mattered there: loading units for a page of products at once to avoid “the N+1 that only shows up on a customer’s 300-product sync”. Even the hybrid search’s reciprocal-rank fusion, which combines two ranked lists, accumulates scores in a dictionary and sorts once, rather than merging.

So the honest lesson from this codebase is the Beginner table in practice: for small, unordered collections, a hash map beats two pointers on clarity, and clarity wins. The two-pointer patterns earn their place where data is ordered and large.

A pointer that only moves forward: the memory sweep

ezychat has a nightly job that reads recent customer messages for each organization in batches and extracts business facts customers keep asking about (“Customers keep asking about parking”, in the module’s own example). It’s a reader pointer over a stream that grows every day, and the module is built around that pointer’s invariants. From the docstring of ai/memory_sweep.py:

The cursor advances only after the work is persisted. A vendor outage, an unusable answer or a failed write all leave it where it was, so tomorrow retries rather than recording the messages as understood.

The pointer is stored per organization as two columns, a timestamp and a message ID, and the next window starts strictly after it:

def _window(org_id: uuid.UUID, from_at: datetime, from_id: uuid.UUID | None) -> Select:
    """...
    The keyset is `(created_at, id)` rather than a timestamp alone: two
    messages sharing a microsecond would otherwise be skipped or re-read,
    and re-reading is the worse of the two, because dedup would fold the
    repeat into an `observation_count` increment and quietly inflate the
    frequency number the whole review surface is ranked by.
    """
    ...
    if from_id is None:
        query = query.where(Message.created_at > from_at)
    else:
        query = query.where(
            or_(
                Message.created_at > from_at,
                and_(Message.created_at == from_at, Message.id > from_id),
            )
        )
    return query.order_by(Message.created_at, Message.id).limit(MESSAGE_CAP)

and only moves after everything downstream has succeeded:

def _advance(state: OrgMemoryState, last_row) -> None:
    state.cursor_at = last_row.created_at
    state.cursor_message_id = last_row.id
    state.last_swept_at = datetime.now(UTC)

Map it onto Expert’s checklist. The precondition is a strict total order, which a timestamp alone doesn’t give you: two messages can share a microsecond, and then “after this timestamp” either skips one or re-reads one. Adding the ID as a tie-breaker makes every message’s position unique. The invariant is “everything at or before the cursor has been understood and stored”, and sweep_org’s docstring says how it’s protected: “The cursor is written last and only on success, so every early return leaves this org’s window intact for the next run.” The variant is the cap: each run reads at most MESSAGE_CAP (400) messages, so a run always ends.

There’s one deliberate exception to “only moves forward one batch at a time”, and the code explains it. An organization receiving more than 400 messages a day would fall further behind every night. So the window’s start is clamped to LOOKBACK_DAYS (14) ago, and a cursor older than that jumps forward:

    horizon = now - timedelta(days=LOOKBACK_DAYS)
    if state is None or state.cursor_at is None:
        return horizon, None, False
    if state.cursor_at < horizon:
        return horizon, None, True
    return state.cursor_at, state.cursor_message_id, False

The comment above LOOKBACK_DAYS calls the unclamped version “a one-way ratchet with no floor”. A pointer that’s allowed to skip data on purpose, with a logged warning when it does, is a design decision, and the code states the trade: the signal is what customers are asking now.

Keyset pagination: the pointer the client holds

The same idea runs every list endpoint in ezychat. The architecture decision record for pagination (ADR-0005 in the handbook) rejects OFFSET and uses a keyset cursor: “The cursor encodes the sort key values of the last item seen”, and the next page is

-- Next page after cursor
WHERE (created_at, id) < (:last_created_at, :last_id)
ORDER BY created_at DESC, id DESC
LIMIT :limit + 1

The client holds the pointer between requests, base64-encoded so clients treat it as opaque and can’t come to depend on the sort columns. The id tie-breaker is there for the same reason as in the memory sweep. The ADR’s rejected alternative is the cost model of a pointer that can’t seek: “OFFSET 10000 scans and discards 10,000 rows”.

A pointer is only as cheap as the order it moves through, and the handbook records one place where that went wrong. The orders CSV export pages through a date range with a keyset cursor, and the existing index put status before created_at, while the export filters status with an inequality. The schema notes say what happened:

the export fell back to a parallel seq scan and a top-N sort on every page — 41 ms a page on the medium profile’s largest tenant, 0.7 ms with this. id is on the end so the keyset cursor seeks rather than filters.

“This” is a partial index on (org_id, created_at, id) that excludes drafts. In this article’s terms: the cursor’s precondition is that the data can be read in key order, and an index in a different order meant every page re-sorted the data to recreate it.

This site’s deploy is a two-pointer diff

The clearest merge in my own stack isn’t in ezychat at all. This site is built by GitHub Actions and uploaded to S3 with two commands from .github/workflows/deploy.yml:

      - name: Upload fingerprinted assets
        run: |
          aws s3 sync dist/_astro s3://tarif-dev-portfolio/_astro \
            --delete \
            --cache-control "public, max-age=31536000, immutable"

(and a second aws s3 sync dist ... --delete for everything else). sync has to work out what to upload and, because of --delete, what to remove: exactly the source-and-replica diff from Expert. I read how the AWS CLI does it, in awscli/customizations/s3/comparator.py (version 2.22.28’s source). The docstring of Comparator.call describes the algorithm:

The key concept in this function is that no matter the type of where the files are coming from, they are listed in the same order, least to greatest in collation order. This allows for easy comparisons to determine if file needs to be added or deleted.

and the loop is the sorted diff, with flags for which side to advance:

                if compare_keys == 'equal':
                    should_sync = self._sync_strategy.determine_should_sync(
                        src_file, dest_file
                    )
                    if should_sync:
                        yield src_file
                elif compare_keys == 'less_than':
                    src_take = True
                    dest_take = False
                    ...
                elif compare_keys == 'greater_than':
                    src_take = False
                    dest_take = True

“Equal” asks the size-and-timestamp strategy whether to re-upload; “less than” means the file is only local, so upload it and advance only the local side; “greater than” means it’s only in the bucket, so delete it and advance only the bucket side. Two listings that could hold millions of keys, compared in one pass without holding either.

The precondition gets the care Expert said it needs. S3 lists keys in byte order of the full key, but a local directory walk sees one folder at a time. If the CLI sorted folder entries by name alone, a folder blog would sort before a file blog-feed.xml, and everything inside blog/ would be listed before the file, while S3, comparing full keys, puts blog-feed.xml first (- is byte 45, / is 47). The comment in filegenerator.py explains the fix: “first going through the current directory contents and adding the directory separator to any directories. We can then sort the contents, and ensure byte order.” In Python:

# S3 lists keys in byte order of the full key. A local walk sees one directory at a time.
s3_keys = sorted(["blog/index.html", "blog-feed.xml", "blog/rss.xml"])
print(s3_keys)

entries = ["blog", "blog-feed.xml"]                 # what listdir() returns at the top level
print(sorted(entries))                               # 'blog' < 'blog-feed.xml': recurse into blog/ first
print(sorted(["blog/", "blog-feed.xml"]))            # with the separator: '-' (45) < '/' (47)
# ['blog-feed.xml', 'blog/index.html', 'blog/rss.xml']
# ['blog', 'blog-feed.xml']
# ['blog-feed.xml', 'blog/']

Without that one appended slash, the merge would see the two sides in different orders and produce exactly the add-then-delete nonsense from the collation example, on a command run with --delete. It’s the best real-world example I know of the rule that a merge is only as correct as its ordering.

What I take from it

• Use a hash map until order is free. Every diff in ezychat’s application code is small and unordered, and sets are the clear choice there. Two pointers is for data that’s already sorted or too big to hold.
• In production, the pointer is a saved position. The memory sweep and keyset pagination are same-direction pointers whose invariant (“everything before here is done”) has to survive crashes and retries. Advance it last.
• Ties break pointers. Both ezychat cursors carry an ID next to the timestamp because “after this time” isn’t a position when two rows share the time.
• The ordering is part of the contract. The AWS CLI appends a slash so its local order matches S3’s; a cursor needs an index in the order it walks. A merge with mismatched ordering doesn’t crash; it returns wrong answers.

Cheat sheet