The Two Pointers Technique in Python: Turning O(n²) Into O(n)

A nested loop over every pair in a list of 1,000 items inspects 499,500 pairs. Two pointers walking that same list inspect at most 999. That gap is not a tuning detail — it is the difference between code you can run on a million items and code you cannot, and it usually costs about four lines.

Two pointers is a pattern rather than a single algorithm. You keep two indices into one sequence and move them under a rule that guarantees each index only ever travels in one direction. Because neither index ever backtracks, the total number of moves is bounded by the length of the sequence, and a problem that looked like it needed every pair collapses into a single sweep.

The catch is that the rule has to be provably safe. Moving a pointer throws away a large set of candidate answers unseen, and that is only legal if none of them could have been the answer. Most of this post is those proofs, because they are the hard part. Once you have the proof, the code writes itself.

The idea

Take a list. Put one index at position 0 and another at position len(values) - 1. Look at the pair they point at. Based on what you see, move one of them inwards. Repeat until they meet.

That is the first shape, converging pointers. The second puts both indices near the front and moves both rightwards under different conditions: one reads every element, the other advances only when something interesting happens. That is same-direction pointers, and the fast-and-slow pair used to find cycles in a linked list is the same shape with a fixed speed ratio.

Both shapes share the property that makes the pattern fast: each pointer moves one way only. In the converging shape left starts at 0 and only increases, right starts at len(values) - 1 and only decreases, and the loop stops the instant they meet. Every turn moves at least one of them, so the body runs at most n − 1 times. If the body costs a constant amount, the algorithm is O(n).

That counting argument is easy. The safety argument is not: why is it correct to move on rather than back up and try the pairs you skipped? The answer differs per problem, and it always comes from some ordering property of the data — which is why most converging-pointer problems need sorted input.

Watching it work

Given a list sorted in ascending order, find two positions whose values add up to a target. Take [1, 3, 4, 6, 8, 11] and a target of 10, with left at index 0 and right at index 5.

• 1 + 11 = 12. Too big. Move right in to index 4.
• 1 + 8 = 9. Too small. Move left in to index 1.
• 3 + 8 = 11. Too big. Move right in to index 3.
• 3 + 6 = 9. Too small. Move left in to index 2.
• 4 + 6 = 10. Found it, at indices 2 and 3.

Five steps. There are 15 distinct pairs in a six-element list, and a nested loop would have stumbled onto this answer on its tenth. But the count is not the interesting bit — the interesting bit is why the skipped pairs never needed checking at all.

Why discarding a whole row is safe

Draw every pair as a table. Rows are the left value, columns are the right value, each cell holds their sum. Only cells where the left index is smaller than the right index are real pairs; the rest are blank.

This table is sorted along both axes, and that follows directly from the list being sorted. Move right along a row: the left value is fixed while the right value grows, so the sums grow. Move down a column: the right value is fixed while the left value grows, so the sums grow again.

Now look at where the algorithm starts — the top-right corner. That cell is simultaneously the largest sum in its row and the smallest sum in its column. Everything follows from that:

• If the corner is too big, it is the smallest entry in its column, so every other sum in that column is bigger still. Nothing there can be the target. Delete the whole column, which is exactly what right -= 1 does.
• If the corner is too small, it is the largest entry in its row, so every other sum in that row is smaller still. Delete the whole row, which is exactly what left += 1 does.

Each step retires a full row or column without looking inside it. There are only n rows and n columns to retire, so the walk ends within 2n steps even though the table holds n(n − 1) / 2 cells. The path is a staircase from the corner down to the answer — the same walk used to search a matrix whose rows and columns are both sorted.

Keep both halves of that in your head. "Two pointers is O(n)" is a fact about the loop; "each move retires a row or a column" is why the loop is allowed to skip that much.

The code

Start with the version that needs no cleverness, so there is something to compare against.

# Postponed annotation evaluation, so `X | None` works on Python 3.9 too.
from __future__ import annotations


def pair_sum_brute_force(values: list[int], target: int) -> tuple[int, int] | None:
    """Return the indices of the first pair that adds to target, or None.

    Works on any list, sorted or not, because it checks every pair.
    """
    size = len(values)
    for left in range(size):
        for right in range(left + 1, size):
            if values[left] + values[right] == target:
                return left, right
    return None


numbers = [1, 3, 4, 6, 8, 11]
print(pair_sum_brute_force(numbers, 10))
print(pair_sum_brute_force(numbers, 100))

(2, 3)
None

Now the two-pointer version, plus a traced copy that prints the walkthrough above so you can check the hand trace against the machine.

def pair_sum(values: list[int], target: int) -> tuple[int, int] | None:
    """Find two indices in an ascending-sorted list whose values add to target.

    Returns the pair of indices, or None if no such pair exists. Runs in O(n)
    time and O(1) space. The list must already be sorted; this does not check.
    """
    left, right = 0, len(values) - 1

    while left < right:
        total = values[left] + values[right]
        if total == target:
            return left, right
        if total < target:
            # Even the largest partner still in play was too small, so no
            # remaining pair that uses values[left] can reach the target.
            left += 1
        else:
            # Even the smallest partner still in play was too large.
            right -= 1

    return None


def pair_sum_traced(values: list[int], target: int) -> tuple[int, int] | None:
    """The same algorithm, printing every step it takes."""
    left, right = 0, len(values) - 1
    while left < right:
        total = values[left] + values[right]
        if total == target:
            verdict = "found"
        elif total < target:
            verdict = "too small, move left in"
        else:
            verdict = "too big, move right in"
        print(f"left={left} right={right}  {values[left]:>2} + {values[right]:>2}"
              f" = {total:>2}  {verdict}")
        if total == target:
            return left, right
        if total < target:
            left += 1
        else:
            right -= 1
    return None


print(pair_sum_traced(numbers, 10))
print(pair_sum(numbers, 100))

left=0 right=5   1 + 11 = 12  too big, move right in
left=0 right=4   1 +  8 =  9  too small, move left in
left=1 right=4   3 +  8 = 11  too big, move right in
left=1 right=3   3 +  6 =  9  too small, move left in
left=2 right=3   4 +  6 = 10  found
(2, 3)
None

The gap between the two grows fast. Here both versions hunt for a target that does not exist in a sorted list of 1,000 even numbers, so neither can exit early, and the counters record how many pairs each one actually inspects.

def count_brute_force(values: list[int], target: int) -> int:
    """How many pairs the nested loops inspect."""
    looks = 0
    for left in range(len(values)):
        for right in range(left + 1, len(values)):
            looks += 1
            if values[left] + values[right] == target:
                return looks
    return looks


def count_two_pointers(values: list[int], target: int) -> int:
    """How many pairs the converging pointers inspect."""
    looks, left, right = 0, 0, len(values) - 1
    while left < right:
        looks += 1
        total = values[left] + values[right]
        if total == target:
            return looks
        if total < target:
            left += 1
        else:
            right -= 1
    return looks


evens = [2 * index for index in range(1000)]
print(count_brute_force(evens, 1), count_two_pointers(evens, 1))

499500 999

How the code maps to the idea

while left < right is strict, not left <= right. With <= the loop eventually reaches a state where both indices point at the same element, and pair_sum would report that element paired with itself — a real bug when the target is exactly twice some value in the list. Strictness also gives the termination proof: the gap shrinks by at least one every turn and the loop stops at zero.

The three-way branch is the staircase walk. Equality is the answer, total < target deletes a row, total > target deletes a column. Exactly one pointer moves per branch, which keeps both claims true: the loop always makes progress, and it never discards a row and a column in the same step.

Nothing is stored. Two integers and a sum, whatever the size of the list, so extra space is O(1). That is often the real reason to prefer it over a lookup table.

Edge cases fall out of the arithmetic. An empty list gives left = 0 and right = -1, so the loop never runs. A one-element list gives left = 0 and right = 0, likewise. Neither needs a guard.

The sorted precondition is not checked, deliberately: checking costs O(n) and defeats the point of a function you call inside a loop. On unsorted input it does not raise, it silently returns the wrong answer — which is worse, so document the precondition and mean it.

The other variants worth knowing

The pair sum is the cleanest example, but the shape shows up in a dozen disguises. These are the ones worth being able to write from memory.

Palindromes

The same converging walk, without the arithmetic. Compare the ends, step inwards, stop the moment they disagree. There is nothing to prove beyond the definition: a string is a palindrome exactly when every character matches its mirror, and the loop checks each mirror pair once.

def is_palindrome(text: str) -> bool:
    """True if text reads the same both ways, ignoring case and punctuation."""
    cleaned = [character.lower() for character in text if character.isalnum()]
    left, right = 0, len(cleaned) - 1

    while left < right:
        if cleaned[left] != cleaned[right]:
            return False
        left += 1
        right -= 1

    return True


for candidate in ["A man, a plan, a canal: Panama", "race a car", "ab", "a", ""]:
    print(f"{candidate!r:34} {is_palindrome(candidate)}")

'A man, a plan, a canal: Panama'   True
'race a car'                       False
'ab'                               False
'a'                                True
''                                 True

Writing this as cleaned == cleaned[::-1] is shorter and, in CPython, faster — the reversal runs in C. The two-pointer version wins on space, because it never builds the second copy, and it bails out on the first mismatch.

Reversing in place

Swap the ends, then close in. The loop runs len(values) // 2 times, exactly the minimum number of swaps needed.

def reverse_in_place(values: list) -> None:
    """Reverse a list by swapping the two ends and closing inwards."""
    left, right = 0, len(values) - 1
    while left < right:
        values[left], values[right] = values[right], values[left]
        left += 1
        right -= 1


letters = list("abcdef")
reverse_in_place(letters)
print("".join(letters))

digits = [1, 2, 3, 4, 5]
reverse_in_place(digits)
print(digits)

fedcba
[5, 4, 3, 2, 1]

In real Python you would write values.reverse(), which is this loop implemented in C. Write it once by hand anyway; it is the smallest version of the pattern there is.

Removing duplicates from a sorted list, in place

This is the same-direction shape. One pointer, read, visits every index. Another, last_kept, marks the end of the answer being built at the front of the same list. Because the list is sorted, equal values are always adjacent, so one comparison against the last value kept decides whether the current one is new.

def remove_duplicates(values: list[int]) -> int:
    """Compact a sorted list in place so that values[:kept] are its distinct
    values, and return kept.

    Everything from index kept onwards is left as whatever happened to be
    there and must be ignored. O(n) time, O(1) extra space.
    """
    if not values:
        return 0

    last_kept = 0
    for read in range(1, len(values)):
        # values is sorted, so a repeat can only ever sit next to the value it
        # repeats. One comparison against the last value kept is enough.
        if values[read] != values[last_kept]:
            last_kept += 1
            values[last_kept] = values[read]

    return last_kept + 1


sample = [1, 1, 1, 2, 3, 3]
kept = remove_duplicates(sample)
print(kept, sample[:kept], sample)

longer = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
kept = remove_duplicates(longer)
print(kept, longer[:kept])

empty: list[int] = []
print(remove_duplicates(empty), empty)

3 [1, 2, 3] [1, 2, 3, 2, 3, 3]
5 [0, 1, 2, 3, 4]
0 []

Notice the printed tail: sample ends up as [1, 2, 3, 2, 3, 3]. The function does not shorten the list, it only guarantees the first kept entries are correct, and forgetting that is the most common bug in this variant. The write pointer can never overtake the read pointer — last_kept starts behind and advances at most once per turn — so nothing is overwritten before it has been read.

Fast and slow

Give the two same-direction pointers a fixed speed ratio instead of a condition and you get a different tool. Advance slow one node per turn and fast two, and when fast falls off the end, slow sits at the midpoint. Run the same pair inside a linked list that loops back on itself and they must collide, because fast closes the gap by exactly one node per turn, so inside a loop of length L they meet within L turns. That is Floyd's tortoise and hare.

class Node:
    """A singly linked list node, here only to demonstrate fast and slow."""

    def __init__(self, value: int) -> None:
        self.value = value
        self.next: Node | None = None


def build_list(values: list[int]) -> Node | None:
    head: Node | None = None
    for value in reversed(values):
        node = Node(value)
        node.next = head
        head = node
    return head


def middle_value(head: Node | None) -> int | None:
    """The value halfway along a linked list, found in a single pass.

    slow advances one node per turn and fast advances two, so fast reaches
    the end after slow has covered exactly half the nodes.
    """
    slow, fast = head, head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow.value if slow is not None else None


def has_cycle(head: Node | None) -> bool:
    """Floyd's tortoise and hare.

    fast closes the gap on slow by exactly one node per turn, so once both are
    inside a loop of length L they must collide within L turns.
    """
    slow, fast = head, head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False


odd_list = build_list([1, 2, 3, 4, 5])
even_list = build_list([1, 2, 3, 4])
print(middle_value(odd_list), middle_value(even_list), middle_value(None))
print(has_cycle(odd_list))

looped = build_list([1, 2, 3, 4, 5])
tail = looped
while tail.next is not None:
    tail = tail.next
tail.next = looped.next  # the last node now points back at the second
print(has_cycle(looped))

3 3 None
False
True

A list of even length has two middles and this version returns the second, which is why [1, 2, 3, 4] prints 3. Cycle detection is where the shape really earns its keep: the obvious alternative, a set holding every node already visited, costs O(n) memory. Two pointers cost two.

Container with most water

Treat each entry in a list of heights as a vertical line and pick the two lines that hold the most water between them. The area of a pair is the distance between them times the height of the shorter one, because water spills over the shorter side.

This is the variant worth studying, because the input is not sorted and the proof still works. Start at the two ends, the widest pair possible. Whichever line is shorter caps the area of every pair it belongs to, and every pair it has left is narrower than the one just measured. Its best remaining area is therefore strictly less than the area already recorded, so it can be discarded — safely, permanently, without looking.

def max_water(heights: list[int]) -> int:
    """The most water two of the vertical lines can hold between them.

    The area of a pair is the distance between the lines times the height of
    the shorter one, because water spills over the shorter side.
    """
    left, right = 0, len(heights) - 1
    best = 0

    while left < right:
        area = (right - left) * min(heights[left], heights[right])
        best = max(best, area)
        # The shorter line caps every rectangle it appears in, and every pair
        # it has left is narrower than this one, so it can never do better.
        if heights[left] < heights[right]:
            left += 1
        else:
            right -= 1

    return best


def max_water_brute_force(heights: list[int]) -> int:
    """Check all n(n - 1) / 2 pairs. Used here only to verify the fast one."""
    best = 0
    for left in range(len(heights)):
        for right in range(left + 1, len(heights)):
            best = max(best, (right - left) * min(heights[left], heights[right]))
    return best


print(max_water([1, 8, 6, 2, 5, 4, 8, 3, 7]))

agree = all(
    max_water(profile) == max_water_brute_force(profile)
    for profile in (
        [(index * index * 7 + offset * 31) % 29 + 1 for index in range(40)]
        for offset in range(300)
    )
)
print("matches the brute force on all 300 profiles:", agree)

49
matches the brute force on all 300 profiles: True

Checking against the quadratic version is not a proof, but it is the right habit. When a linear algorithm claims to match an exhaustive one, run both on a few hundred inputs before believing yourself.

3-sum: fix one, two-pointer the rest

Find every distinct triple that adds to zero. The exhaustive version is three nested loops, O(n³). The fix is to stop treating it as a three-dimensional problem: sort the list, fix the first value, and what remains is "find two values that add to minus the fixed one" — the pair sum you already have.

Sorting does double duty. It makes the inner sweep legal, and it puts equal values next to each other so duplicate triples are cheap to skip.

def three_sum(values: list[int]) -> list[tuple[int, int, int]]:
    """Every distinct triple of values that adds to zero, smallest first.

    Sorting is what makes the inner two-pointer sweep legal, and it is also
    what makes duplicates cheap to skip: equal values end up side by side.
    """
    numbers_sorted = sorted(values)
    size = len(numbers_sorted)
    triples: list[tuple[int, int, int]] = []

    for first in range(size - 2):
        if numbers_sorted[first] > 0:
            break  # three numbers all above zero cannot add to zero
        if first > 0 and numbers_sorted[first] == numbers_sorted[first - 1]:
            continue  # this value has already been the fixed element

        left, right = first + 1, size - 1
        while left < right:
            total = numbers_sorted[first] + numbers_sorted[left] + numbers_sorted[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                triples.append(
                    (numbers_sorted[first], numbers_sorted[left], numbers_sorted[right])
                )
                left += 1
                right -= 1
                while left < right and numbers_sorted[left] == numbers_sorted[left - 1]:
                    left += 1
                while left < right and numbers_sorted[right] == numbers_sorted[right + 1]:
                    right -= 1

    return triples


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

[(-1, -1, 2), (-1, 0, 1)]
[(0, 0, 0)]
[]
[(-2, 0, 2), (-2, 1, 1)]

The break on the first positive value is a small win worth understanding: once the smallest of the three is above zero, all three are, so no triple from here on can reach zero. On a list of mostly positive numbers that ends the outer loop almost immediately.

Complexity

The converging sweep is O(n). Each turn does a fixed amount of work — one addition, one comparison, one increment — and moves exactly one pointer. The two pointers share a single budget: the gap between them starts at n − 1 and shrinks by one per turn, so the loop runs at most n − 1 times. There is no hidden cost inside the body.

Space is O(1). Two indices and a running total, regardless of input size. The palindrome version is the one exception, since it builds a cleaned list first; skip non-alphanumerics inline and it is O(1) too.

Sorting, when you need it, dominates. If the input arrives unsorted, the honest bound for the pair sum is O(n log n) for the sort plus O(n) for the sweep, which is O(n log n). The log comes from the sort: merge sort and the Timsort behind Python's sorted() both halve the problem repeatedly, giving log₂ n levels, and each level touches all n items. Do not quote O(n) for a function that sorts first.

3-sum is O(n²). The outer loop fixes each of n values in turn, and each one costs an O(n) sweep: n × n. The sorted() call adds O(n log n), which n² swallows. That is a big improvement on the O(n³) triple loop, but it is still quadratic — 10,000 inputs means roughly 100 million inner steps.

Fast and slow is O(n) time and O(1) space. fast advances two nodes per turn and falls off the end within n / 2 turns; with a cycle it collides within one extra lap.

Here is the comparison that matters, on the pair sum with the input already sorted:

Ten times the data costs a hundred times the work on the left and ten times on the right. At 100,000 items that is exactly 50,000 times fewer steps.

When to use it, and when not to

Use it when the input is sorted (or you can sort it cheaply), the answer is a pair of positions rather than a range, and extra space has to stay constant. Sorted arrays, strings compared from both ends, in-place compaction and merging two sorted sequences are all natural fits.

Do not use it on unsorted input just because the shape is familiar. For "do two values add to this target" on unsorted data, one pass with a set is better: O(n) time and no sort at all. It costs O(n) memory, and that is the trade. Two pointers only win when the data is already sorted or memory is genuinely tight. Hash tables explain why that lookup is O(1).

Do not use it when the answer is a contiguous run. That is the sliding window, which is a two-pointer method too — both ends move rightwards — but the question is different. A window cares about everything between its ends: the sum of the run, the number of distinct characters in it, whether it is still valid. Converging pointers care about the pair itself and mostly ignore what sits between them. If the answer is a subarray or substring, reach for a window; if it is two positions, reach for two pointers.

Do not use it when the property you rely on is not monotonic. The pattern rests entirely on "moving this pointer can only change things in one predictable direction". If moving left could send the sum either way, the safety proof collapses and the algorithm returns wrong answers without complaining.

Where it shows up in the real world

Merging sorted sequences. The merge step of merge sort is two pointers, one into each of two sorted halves, each advancing when its value is taken. The same walk is a sort-merge join in relational databases: PostgreSQL's Merge Join advances a cursor over each of two sorted inputs, taking whichever key is smaller. It is also how LSM-tree storage engines such as RocksDB and LevelDB compact several sorted files into one.

CPython's string stripping. str.strip() walks an index forward from the start while the character is whitespace, then walks a second index backward from the end under the same test, and slices between them. It is a converging pair with a very simple rule.

Mark-compact garbage collectors. Sliding compaction walks the heap with a read pointer and a write pointer, copying every live object down over the dead ones, exactly like the in-place deduplication above. The write pointer trails the read pointer, so no live object is overwritten before it has been moved.

Pollard's rho factorisation uses Floyd's tortoise and hare to detect the cycle in the pseudo-random sequence it generates. That is what lets it run in constant memory instead of storing every value it has seen.

Common mistakes

Feeding it unsorted input. pair_sum([8, 1, 3], 4) returns None. Trace it: 8 + 3 = 11 is too big so right moves to index 1, then 8 + 1 = 9 is still too big so right moves to index 0, and the loop ends — even though 1 + 3 is exactly 4. No exception, just a wrong answer. Sort first, or use a set.

Using left <= right. The loop then compares an element with itself. For pair_sum([2, 5, 7], 10) that would report indices 1 and 1 as a valid pair for the target 10.

Moving both pointers on a mismatch. It feels symmetric and it is wrong. On [2, 3, 4, 5] with target 8, the correct walk goes 2 + 5 = 7 (too small, move left) then 3 + 5 = 8 and finds it. Moving both jumps straight to 3 + 4 = 7, then the pointers cross and the answer is missed.

Forgetting a branch that moves nothing. Every path through the loop body must advance a pointer or return. A condition that leaves both indices untouched is an infinite loop, and it is the failure mode you will hit first when adapting the pattern to a new problem.

Treating the in-place result as a shortened list. remove_duplicates returns a count, and the entries past that count are stale. Always slice with the returned length.

Skipping duplicate handling in 3-sum. Without the continue for a repeated fixed value, [-1, -1, 0, 1, 1] yields the triple (-1, 0, 1) twice — once for each -1 in the input. The skips are not an optimisation, they are part of the specification.

Practice

1. Given a sorted list and a target, count how many index pairs add to that target, including when the same value appears more than once.
2. Move every zero in a list to the end while keeping the order of the non-zero values, in one pass with O(1) extra space.
3. Merge two already-sorted lists into one sorted list using one pointer into each, without calling sorted().
4. Given a list sorted in ascending order that may contain negatives, return the squares of its values in sorted order in O(n) — the trick is to fill the output from the back.
5. Given a list of bar heights, compute the total rainwater trapped between them using two converging pointers and a running maximum from each side.

Summary

Two pointers turns a quadratic search over pairs into a linear sweep by making each step retire an entire row or column of the pairs you never have to check. The loop bound is easy — neither index backtracks, so the body runs at most n times — and the real work is the safety proof that lets you move a pointer at all. Learn the staircase argument on the sorted pair sum, then notice the same shape in palindromes, in-place compaction, cycle detection and the container problem.

Keep reading

• Merge Sort — its merge step is two pointers over two sorted lists, and it is where the O(n log n) sorting cost comes from.
• Linked Lists — build the structure that fast and slow pointers traverse, including cycles.
• Big O Notation — the counting arguments used throughout this post, from first principles.