Two Pointers

TL;DR

When a brute-force solution looks like a double for loop over the same array, ask: can I replace one of those loops with a second pointer that only ever moves forward? If yes, you’ve turned O(n²) into O(n) and the problem is done.

The pattern shows up in two flavors:

• Opposite ends — left starts at 0, right at n - 1, they walk toward each other. Used when the array is sorted and you’re hunting for a sum, difference, or some symmetric condition.
• Same direction — slow and fast both start near the front; fast scans, slow writes. Used for in-place dedupe, partitioning, and “compact the array” problems.

Both flavors share one rule: each pointer only moves O(n) total times across the entire run, which is what gives you the linear bound.

The picture in your head

Imagine a sorted shelf of books, each with a price sticker, and you want to find two books whose prices add up to exactly $100. Brute force: pull every pair off the shelf, check the sum, put them back. With 1,000 books that’s half a million pulls. Two pointers: stand a clerk at each end of the shelf. If the sum is too small, the left clerk moves right by one book. If too big, the right clerk moves left. Each clerk only ever walks the shelf once — so 2,000 moves total, not 500,000. The shelf being sorted is the entire trick: when the sum is too small, every book to the left of the right clerk’s position is also too small, so they’re safely skipped without checking. That’s the pattern.

The problem it solves

A huge class of array and string problems looks like this: “find a pair (or in-place rearrangement) of elements in nums that satisfies condition X.” The textbook brute force is two nested loops:

for i in range(n):
    for j in range(i + 1, n):
        if condition(nums[i], nums[j]):
            ...

That’s O(n²) time and O(1) space. At n = 10⁴, you’re doing 50 million comparisons — fine for an interview, dead in production. At n = 10⁶, it’s 10¹² operations — your function never returns within a useful timeout.

Two pointers asks one question of the brute force: “do I really need every pair, or is there an order in which moving one pointer monotonically rules out a whole region of pairs?” When the answer is yes (almost always when the input is sorted, or when you can sort it cheaply), the inner loop collapses into a second pointer that only walks O(n) total. You’ve kept the O(1) space of the brute force while dropping time from O(n²) to O(n) — the rare trade where you give up nothing.

When to reach for it

Signals that two pointers is probably the right move:

• The input is sorted (or you can afford to sort it) and the question is about pairs, triplets, or ranges.
• You need to modify the array in place without allocating a second one.
• A naive solution walks every pair (i, j) with i < j — O(n²) — and you realise that for a fixed i, the inner loop can be replaced by a pointer that monotonically moves.
• The problem mentions “without extra space” or a target memory of O(1).

Signals that it’s not two pointers: the array is unsorted and order matters, the relationship between elements isn’t monotonic, or the answer requires revisiting elements (you’d want a hash map or sliding window instead).

Flavor 1 — opposite ends: pair sum on a sorted array

Given a sorted array and a target, find two indices whose values sum to the target.

def pair_sum(nums: list[int], target: int) -> tuple[int, int] | None:
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return (left, right)
        if s < target:
            left += 1   # need a larger sum → move left up
        else:
            right -= 1  # need a smaller sum → move right down
    return None

Worked example. nums = [1, 3, 4, 6, 8, 11], target = 10.

The invariant: any pair we skipped by moving left up was already too small (its right partner is the largest remaining), and any pair we skipped by moving right down was already too big. So we never miss a valid answer. That’s why the linear scan suffices.

Flavor 2 — same direction: in-place dedupe

Given a sorted array, remove duplicates in place and return the new length.

def dedupe(nums: list[int]) -> int:
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

Worked example. nums = [1, 1, 2, 2, 2, 3, 4, 4].

Return slow + 1 = 4. The first four slots of nums are the deduped result; the trailing entries are garbage you ignore. No extra array allocated.

This same skeleton — slow writes, fast reads — solves “remove element”, “move zeros to end”, and “partition by predicate”. The only thing that changes is the condition under which slow advances and writes.

Flavor 1 extended — three sum

The trick that makes three-sum tractable: fix the first element, then run two-pointer on the rest.

def three_sum(nums: list[int]) -> list[tuple[int, int, int]]:
    nums.sort()
    out = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # skip duplicate anchors
        left, right = i + 1, len(nums) - 1
        target = -nums[i]
        while left < right:
            s = nums[left] + nums[right]
            if s == target:
                out.append((nums[i], nums[left], nums[right]))
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1   # skip duplicate lefts
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1  # skip duplicate rights
            elif s < target:
                left += 1
            else:
                right -= 1
    return out

The outer loop is O(n), the inner two-pointer scan is O(n), so the whole thing is O(n²) — better than the O(n³) naive triple loop, and it’s the same template you’ll reuse for four-sum (one more outer loop) and k-sum (recursion + the same base case).

Why it works — the invariant

Two-pointer correctness rides on a single idea: at every step, moving a pointer eliminates a whole region of the search space that you can prove contains no answer. In pair-sum-on-sorted-array, when the sum is too small and you move left++, you’re not just trying the next pair — you’re killing all pairs (left, k) for k ≤ right, because every one of them is at least as small as the current pair you already showed was too small.

If you can’t articulate that elimination argument for your problem, the pattern probably doesn’t apply. Force yourself to write down the invariant before coding — it’s how you avoid off-by-one bugs and infinite loops.

Complexity & memory tradeoffs

The reason two pointers is so prized: among the linear-time solutions to pair-search problems, it’s the only one with O(1) extra memory. A hash map gives you the same O(n) time but costs O(n) memory — which matters on embedded systems, in tight inner loops where cache misses dominate, and any time you’re processing arrays large enough that allocating a second one is the bottleneck. If you can sort cheaply (or the input is already sorted), two pointers strictly dominates the hash-map approach.

Common pitfalls

• Forgetting to sort. The opposite-ends flavor only works on sorted input. If you can’t sort (because indices matter), reach for a hash map.
• Wrong loop condition. left < right for opposite ends; left <= right if the answer can include the pivot itself (e.g. palindrome check on odd-length strings). One off-by-one here breaks everything.
• Moving both pointers when you shouldn’t. In pair-sum, on a hit you return; in three-sum, on a hit you advance both pointers and skip duplicates. Mixing those up is the most common bug.
• Same-direction slow semantics. slow is the index of the last written element, so the result length is slow + 1, not slow. Decide on day one whether slow points at “next slot to write” or “last written” and stay consistent — most off-by-ones live here.

Where you see this in production

The pattern shows up far beyond LeetCode. A few real systems that lean on it:

• Vector database posting-list merge. Two sorted ID lists from a hybrid search (BM25 + vector similarity) get merged with the opposite-ends two-pointer walk — same skeleton as pair_sum.
• Log dedupe in streaming pipelines. When a Kafka consumer reads sorted event batches and needs to drop duplicates by (user_id, event_id), the same-direction slow/fast skeleton is the in-place dedupe step.
• Token alignment in tokenizers. Aligning two token sequences (source and BPE-rewritten target) walks both with monotonic pointers — see Hugging Face’s BatchEncoding.word_ids implementation.

Practice problems

A short, ordered set. Each problem hits a flavor of the pattern that the previous one didn’t — solve in order.

If you can write all six from scratch without referencing this page, you own two pointers.

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for every problem in the table above.
• Back To Back SWE — Two Pointers — @BackToBackSWE — alternative explanations when a NeetCode walkthrough doesn’t click.