🧩 Data Structures & Algorithms · Chapter 4

Two pointers

Checking every pair in a sorted list of 10,000 numbers is 50 million comparisons. Two fingers walking inward from the ends do it in under 10,000 — with no extra memory.

Study this lesson free in the app →

The basics

Two pointers is a technique where two indices move through an array (or string) together, each step deciding which one to move, so the whole job finishes in a single pass.

The problem it solves: many questions ask about pairs — two numbers that sum to a target, matching characters at both ends, two sorted lists to merge. Trying every pair is O(n²). If the data has structure — usually sorted order — each comparison tells you which pointer to move, and every move rules out an item for good. Total moves ≤ n, so O(n) time and O(1) extra space.

The mental model: paying exactly 30 with two items from a shelf sorted by price. Hold the cheapest in your left hand and the dearest in your right. Too expensive? Swap the right-hand item for the next cheaper one. Too cheap? Swap the left for the next dearer one. You never need to reconsider an item you've put back.

Explained

"Is there a pair in this sorted list that adds up to 100?"

The obvious answer tries every pair: for 10,000 numbers, about 50 million checks.

Put one finger on the smallest number and one on the largest. Too big? Move the right finger left. Too small? Move the left finger right. At most 9,999 moves, and you've provably checked every pair that could work.

Two items, one exact budget

You have a gift card for exactly 30 and want to spend all of it on two items. The shop shelf is sorted by price: 4, 7, 11, 13, 19, 26.

Pick up the cheapest (4) and the dearest (26): 30. Done in one look.

Now say the shelf were 4, 7, 11, 13, 19, 28. Cheapest + dearest = 32, too much. The 28 can't work with anything — even the cheapest item overshoots — so put it back for good. Now 4 + 19 = 23, too little. The 4 can't work with anything left — even the dearest remaining item falls short — so put it back for good. 7 + 19 = 26, too little; drop the 7. 11 + 19 = 30.

Every look eliminates one item permanently. That's the whole trick.

Why it never misses an answer

Sorted array a, left = 0, right = n − 1, target T. Compare s = a[left] + a[right]:

• s == T → found.
• s < T → a[left] paired with the largest remaining value is still too small, so it's too small with every other value too. Discard it: left += 1.
• s > T → a[right] paired with the smallest remaining value is still too big, so discard it: right -= 1.

Invariant: any valid pair lies entirely inside [left, right]. It's true at the start, and each step only throws away an element that can't be part of a solution. When left == right, no pair remains — so "not found" is a proof, not a guess.

Cost: each step moves one pointer inward, so at most n − 1 steps: O(n) time, O(1) space. Compare brute force at O(n²), or a hash set at O(n) time but O(n) space.

Pair found: target 11

1 + 19 = 20, too big: drop 19. 1 + 15 = 16, drop 15. 1 + 12 = 13, drop 12. 1 + 9 = 10, too small: now drop the 1. 2 + 9 = 11 — found in 5 steps. Notice the right pointer did most of the walking while the sums were too big.

No pair: target 18

Same array, target 18. The pointers zig-zag — 20, 16, 17, 19, 16, 19, 16 — until both land on 9 after 7 comparisons. No pair sums to 18, and because each step discarded an element that couldn't work, meeting in the middle proves it. Brute force would have needed all 28 pairs.

Three shapes of the pattern

def pair_sum(a, target):               # sorted input
    left, right = 0, len(a) - 1
    while left < right:
        s = a[left] + a[right]
        if s == target:
            return left, right
        if s < target:
            left += 1                    # need bigger
        else:
            right -= 1                   # need smaller
    return None                          # O(n) time, O(1) space

def is_palindrome(s):                  # opposite ends
    l, r = 0, len(s) - 1
    while l < r:
        if s[l] != s[r]:
            return False
        l += 1
        r -= 1
    return True                          # O(n) time, O(1) space

def merge(a, b):                       # one pointer per sorted list
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    return out + a[i:] + b[j:]           # O(n + m) time and space

Complexity, and when to pick it

| Approach to pair-sum | Time | Extra space | Needs | | --- | --- | --- | --- | | Check every pair | O(n²) | O(1) | nothing | | Hash set of seen values | O(n) | O(n) | hashable values | | Two pointers | O(n) | O(1) | sorted input | | Sort, then two pointers | O(n log n) | O(1)–O(n) for the sort | can reorder |

My rule: already sorted → two pointers, no contest. Unsorted and you need original indices → hash map. Unsorted and memory is tight (a huge array on a small device) → sort in place, then two pointers.

The pattern also scales up: three-sum is "fix one item, two-pointer the rest" — O(n²) instead of O(n³) — and merging two sorted files of a billion lines each streams through both with constant memory, which is exactly how external merge sort and database merge joins work.

Gotchas

• Running it on unsorted data — the "move left means bigger" logic breaks and it silently misses pairs.
• while left <= right for pair problems — lets an element pair with itself (a[i] + a[i]). Use <.
• Sorting, then returning indices — they're indices into the sorted copy, not the original.
• Forgetting to move a pointer in some branch — an infinite loop.
• Duplicates in three-sum — skip equal neighbours or you'll report the same triplet several times.
• Moving both pointers on a mismatch — in pair-sum, only the pointer that can't be part of any answer moves.

Words to know

In two minutes

• Two indices move through the data in one pass; each comparison decides which one moves. O(n) time, O(1) extra space.
• Opposite ends on a sorted array: sum too small → move left up (bigger); too big → move right down (smaller). Each move discards one value that can't be in any answer.
• Read/write pointers filter or dedupe in place: read visits everything, write only advances for keepers.
• Merging two sorted lists uses one pointer each and always takes the smaller head: O(n + m).
• The pattern needs structure — usually sorted input. On unsorted data, sort first (O(n log n)) or use a hash map (O(n) time, O(n) space).
• Sorting first loses the original indices; if the question wants indices, use a hash map or sort (value, index) pairs.
• Three-sum = sort + for each item, a two-pointer scan of the rest → O(n²), down from O(n³).

Test yourself

There are 9 questions, 4 puzzles and 5 recall cards for this lesson in the app — the recall cards come back on later days, just before you would forget.