Two Pointers

The two-pointers technique uses two indices that walk through the same array (or two arrays in lockstep) to reduce a nominally O(n²) problem to O(n). The two pointers can move in opposite directions (one from each end, converging toward the middle), in the same direction at different speeds (the fast/slow pattern that powers cycle detection), or as a partition cursor (sweeping a write head ahead of a read head). Recognizing which variant the problem demands is more than half the battle; the implementation is usually short and uniform once the pattern is named.

1. Intuition — Two Hands on a Sorted Bookshelf

Imagine you have a bookshelf of price-tagged books sorted left-to-right cheapest-to-most-expensive, and you want to find two whose combined price is exactly $50.

A brute-force shopper picks every pair of books — n × (n-1) / 2 pairs — and checks each sum. That’s O(n²).

A smarter shopper puts one hand on the cheapest book on the left and one hand on the most expensive book on the right. They look at the combined price:

• If the sum is too high, the most expensive book is too expensive — slide the right hand left to a cheaper book.
• If the sum is too low, the cheapest book is too cheap — slide the left hand right to a more expensive book.
• If the sum is exactly $50, found.

Each hand moves at most n times before they meet in the middle, so the whole procedure is O(n). The sortedness of the shelf is what makes the decision “move left or move right” deterministic. Sortedness + monotone decision rule = two pointers can prune.

That’s the whole pattern in miniature. Every two-pointer problem is a variation on “two cursors, structured input, decision rule that monotonically advances at least one cursor.”

2. Tiny Worked Example — Pair Sum on Sorted Array

Given the sorted array arr = [1, 3, 4, 6, 8, 11] and target = 10, find two indices i, j with arr[i] + arr[j] == target.

Step	left	right	arr[left]	arr[right]	sum	Action
1	0	5	1	11	12	sum > 10, decrement right
2	0	4	1	8	9	sum < 10, increment left
3	1	4	3	8	11	sum > 10, decrement right
4	1	3	3	6	9	sum < 10, increment left
5	2	3	4	6	10	Found! Return (2, 3)

Five steps, six elements. The brute-force enumeration would have checked 6 choose 2 = 15 pairs. The pruning is real, and it scales: for n = 10⁶, brute force does ~5 × 10¹¹ comparisons (minutes to hours); two pointers does ~10⁶ (milliseconds).

3. The Pattern Recognition Signal

You should reach for two pointers when any of these phrases appear in the problem statement:

1. “In a sorted array…” combined with pair, triplet, closest sum, or target sum.
2. “Find two/three/k elements such that…” on a sorted (or sortable) input.
3. “In-place modification” of an array — remove duplicates, partition by predicate, move zeros, Dutch flag.
4. “Palindrome” check — opposite-end pointers comparing characters.
5. “Reverse the array/string in place.”
6. “Container with most water,” “trapping rain water,” anything where the answer is a function of two boundary positions.
7. “Without using extra space,” “O(1) extra memory,” on a problem that has an obvious O(n) hash-set solution — the constraint is shouting “use two pointers instead.”
8. Linked-list problems involving cycle, middle, k-th from end, or intersection — the same-direction fast/slow variant. (See Linked List Cycle Detection.)

The inverse signal — when not to use two pointers: the array is unsorted and sorting would destroy required information (e.g., you need original indices), and the problem allows extra space. In that case Hash Table is usually cleaner: pair-sum in unsorted O(n) time and O(n) space via a complement lookup.

The classic interview riddle: “Two Sum” on an unsorted array. Hash table is the textbook answer (O(n)/O(n)). If the input is sorted, two pointers wins (O(n)/O(1)). The tradeoff is space-for-sortedness.

4. Pseudocode — The Three Sub-patterns

4.1 Opposite-End (Converging Pointers)

opposite_end(arr, target):
    left  := 0
    right := length(arr) - 1
    while left < right:
        if condition_satisfied(arr[left], arr[right]):
            return (left, right)
        else if should_move_left_inward(arr[left], arr[right]):
            left := left + 1
        else:
            right := right - 1
    return NOT_FOUND

4.2 Same-Direction (Fast / Slow)

fast_slow(seq):
    slow := start
    fast := start
    while fast not at end:
        slow := advance_slow(slow)
        fast := advance_fast(fast)        # e.g., 2 steps for cycle detect
        if some_condition(slow, fast):
            return ...

4.3 Partition (Read Head / Write Head)

partition(arr, predicate):
    write := 0                            # next write position
    for read in 0 .. length(arr) - 1:
        if predicate(arr[read]):
            swap(arr[write], arr[read])
            write := write + 1
    return write                          # number of elements satisfying predicate

The partition variant is the in-place workhorse: remove duplicates, move zeros to end, partition around a pivot (Quicksort’s Lomuto/Hoare schemes are partition pointers), Dutch national flag.

5. Python Implementation

5.1 Pair Sum (Sorted, Opposite-End)

def pair_sum_sorted(arr: list[int], target: int) -> tuple[int, int] | None:
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return (left, right)
        elif s < target:
            left += 1                # need a bigger sum
        else:
            right -= 1               # need a smaller sum
    return None

5.2 3Sum — Two Pointers Inside a Loop

The classic 3Sum problem (LC 15) reduces to “for each fixed first element, find a 2Sum in the remaining sorted suffix.” That outer loop plus inner two-pointer scan gives O(n²) — much better than the naive O(n³).

def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    res, n = [], len(nums)
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue                                   # skip duplicate first elements
        left, right = i + 1, n - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == 0:
                res.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1                          # skip duplicate seconds
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1                         # skip duplicate thirds
            elif s < 0:
                left += 1
            else:
                right -= 1
    return res

The deduplication-by-skipping is the most common bug source. Notice the three independent skip loops — duplicates of the first, the second, and the third element each need their own guard. Forgetting any one yields duplicate triplets in the output.

5.3 Container With Most Water (LC 11)

def max_area(heights: list[int]) -> int:
    left, right = 0, len(heights) - 1
    best = 0
    while left < right:
        h = min(heights[left], heights[right])
        best = max(best, h * (right - left))
        # move the *shorter* side inward — the only way to possibly improve
        if heights[left] < heights[right]:
            left += 1
        else:
            right -= 1
    return best

The non-obvious step is which pointer to move. Moving the taller side can only shrink the width without raising the bounding height (the shorter side still bounds the rectangle), so it can never improve the answer. Moving the shorter side at least gives a chance.

5.4 Remove Duplicates In Place (LC 26, Partition Pattern)

def remove_duplicates(arr: list[int]) -> int:
    if not arr:
        return 0
    write = 1
    for read in range(1, len(arr)):
        if arr[read] != arr[read - 1]:
            arr[write] = arr[read]
            write += 1
    return write                                       # new logical length

read sweeps every element exactly once; write advances only when a new distinct value is seen. The interview value here is the in-place aspect — no extra array.

5.5 Dutch National Flag — Three-Way Partition (LC 75)

A 1976 problem of Edsger W. Dijkstra: sort an array of three colors (or three values 0/1/2) in one pass with O(1) space. Three pointers (low, mid, high) partition the array into [0…low) = 0s, [low…mid) = 1s, [mid…high] = unknown, (high…end] = 2s.

def sort_colors(nums: list[int]) -> None:
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:                                          # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1                                  # do NOT advance mid here
    # invariant: when mid > high, the array is fully partitioned

Watch the asymmetry: when we swap a 2 to the back, we don’t advance mid because the value just swapped in from nums[high] is still unclassified. When we swap a 0 to the front, we do advance mid because the value swapped in came from nums[low], which we already scanned (it must have been a 1, or mid would have stopped earlier).

6. Complexity

Time: O(n). Each pointer takes at most n steps, and after every iteration of the loop body at least one pointer makes monotone progress. The total number of iterations is therefore bounded by 2n (opposite-end) or n (same-direction, partition). Constant work per iteration ⇒ O(n).

Space: O(1). No auxiliary data structures (assuming the input array is already provided). When you sort the input first (e.g., for 3Sum), the sort itself dominates: the algorithm becomes O(n log n) time and O(log n) recursive stack space for the sort.

Why this beats brute force. Brute force on pair-sum is O(n²) — n choose 2 ≈ n²/2 pairs to inspect. Two pointers exploits the sortedness: every pointer move definitively eliminates a whole class of pairs from further consideration. Incrementing left past index i says “any pair involving the old arr[left] and any element to the right of the new right cannot be the answer” — that’s a 2D region of (i, j) pairs eliminated in one step.

The hash-set alternative for pair-sum is also O(n) time but uses O(n) space and requires a hash. Two pointers wins when the input is already sorted (no extra log-factor) and space is constrained.

7. Variants and Sub-patterns Worth Knowing

7.1 K-Sum

k-Sum generalizes 2Sum and 3Sum: find k numbers summing to a target. The classical recursive formulation: sort the array, then recursively reduce kSum to (k-1)Sum until you bottom out at 2Sum, which uses two pointers. Time complexity is O(n^(k-1)) — for 4Sum that’s O(n³), still polynomial, much better than the O(n^k) brute force.

7.2 Closest-Sum Variants

“3Sum closest” (LC 16): find three elements whose sum is closest to a target. Same outer-loop + inner-two-pointers structure; replace exact-match with if abs(s - target) < abs(best - target): best = s. The pointer-movement rule is unchanged because the direction you’d move to get closer to target is still determined by sign(s - target).

7.3 Trapping Rain Water (LC 42)

A canonical opposite-end problem with a twist. Maintain left_max and right_max and walk the shorter side inward — the water trapped above each bar is determined by the smaller of the two side maxima.

def trap(h: list[int]) -> int:
    left, right = 0, len(h) - 1
    lmax = rmax = water = 0
    while left < right:
        if h[left] < h[right]:
            lmax = max(lmax, h[left])
            water += lmax - h[left]
            left += 1
        else:
            rmax = max(rmax, h[right])
            water += rmax - h[right]
            right -= 1
    return water

The reasoning is identical to “Container With Most Water” — the shorter side bounds the answer, so you advance the shorter side because the other side cannot improve until the shorter one does.

7.4 Same-Direction (Fast/Slow) on Linked Lists

The fast/slow pointer is a two-pointers special case where both pointers walk a linked list at different speeds. Three classic uses:

• Cycle detection — fast moves 2 steps, slow moves 1; they meet inside any cycle. Full treatment in Linked List Cycle Detection.
• Middle of list — when fast hits the end, slow is at the middle. (One pass, no length precomputation.)
• K-th from end — start fast k steps ahead, then walk both at the same speed; when fast hits end, slow is k from end.

The same-direction array variant is the partition/sliding-window cursor pair (see Sliding Window for the windowing case).

7.5 Two Arrays in Lockstep — Merge

The merge step of Merge Sort is a two-pointer walk over two sorted arrays, copying the smaller front element each step. Same pattern, two physical arrays instead of one logical array with two indices. “Intersection of two sorted arrays,” “merge sorted lists,” and “smaller numbers after self” are variations.

7.6 In-Place Reversal

def reverse_in_place(arr: list) -> None:
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

Palindrome check is structurally identical: walk inward, return False on the first mismatch, True if you cross.

8. Pitfalls

8.1 Off-by-One on the Loop Condition

Should the loop be while left < right or while left <= right? Almost always <. Using <= means you process the case left == right, which on a single-element window doesn’t make sense for pair-finding (you’d be summing an element with itself). For palindrome and reversal, < and <= both terminate, but < is fewer iterations (the middle element doesn’t need to swap with itself).

8.2 Forgetting to Skip Duplicates in K-Sum

In 3Sum, after finding a valid triplet, you must advance past duplicates of the second and third elements before continuing the inner loop, and skip duplicates of the first element in the outer loop. Three independent skip loops (see §5.2). This is the most common LeetCode 3Sum failure: getting the right answer plus duplicates of it.

8.3 Moving the Wrong Pointer

In Container-With-Most-Water (§5.3), moving the taller pointer is a correctness bug, not just a performance one. The shorter side bounds the rectangle height; only by moving the shorter side can the bounding height ever rise, so only that move can yield a strictly better candidate. Get the pointer-movement direction right by reasoning about what could possibly improve the answer.

8.4 Dutch Flag Asymmetry

In sort_colors (§5.5), incrementing mid after swapping a 2 to the back is wrong: you haven’t yet inspected the element you swapped in. Conversely, not incrementing mid after swapping a 0 to the front is also wrong: you’ve already inspected what came from nums[low] (it was guaranteed a 1, given the invariant). Asymmetric updates trip people up the first 100 times they write this; trace through [2, 0, 1] by hand once and the rule sticks.

8.5 Assuming Sortedness You Don’t Have

Two pointers on unsorted data returns garbage silently. If the problem says “given an array” without “sorted,” you either (a) sort it first (acceptable for pair-sum, not if you need original indices), or (b) reach for Hash Table instead. Always confirm the precondition.

8.6 Moving Both Pointers When Only One Should Move

In the opposite-end pair-sum, after finding a match, advancing both pointers can skip another valid pair adjacent to the first. For “find all pairs,” advance both and run the duplicate-skip loops. For “find any pair,” return immediately and the question is moot. Read the problem statement: any vs. all changes the post-match logic.

8.7 Linked-List Fast Pointer Null Check

In the fast/slow linked-list idiom, the loop condition must be while fast and fast.next (not just while fast). Otherwise fast.next.next dereferences null. Lists of even length end with fast == None; odd length end with fast.next == None. Both must be guarded. This is the most common runtime crash in cycle-detection submissions.

9. Diagram — The Three Variants Side by Side

flowchart TD
    subgraph "Opposite-end (converging)"
        OA["[L........R]"] --> OB["[ L......R ]"] --> OC["[  L....R  ]"] --> OD["[   L..R   ]"]
    end
    subgraph "Same-direction (fast/slow)"
        SA["S F . . . . ."] --> SB[". S . F . . ."] --> SC[". . S . . F ."]
    end
    subgraph "Partition (write/read)"
        PA["[W R . . . . .]"] --> PB["[. W . R . . .]"] --> PC["[. . W . . R .]"]
    end

What this diagram shows. Three rows depict the three two-pointer variants. The top row shows opposite-end pointers (L, R) closing in toward each other — used for sorted-array pair-sum, palindrome, container-with-most-water. The middle row shows same-direction pointers where fast (F) outruns slow (S) — used for cycle detection, finding the middle, k-th-from-end. The bottom row shows the partition variant where a fast read head (R) sweeps past elements and a slow write head (W) advances only when a write occurs — used for in-place dedup, move-zeros, and partition-by-predicate. The visual pattern of pointer motion is the mnemonic; pick the variant whose motion-shape matches the problem’s required cursor behavior.

10. Common Interview Problems

#	Problem	Variant	Notes
LC 1	Two Sum (unsorted)	Hash Table preferred	Two pointers needs sort first
LC 167	Two Sum II (sorted input)	Opposite-end	Canonical
LC 15	3Sum	Opposite-end inside outer loop	Watch dedup
LC 16	3Sum Closest	Opposite-end	Track best diff
LC 18	4Sum	Recursive k-Sum	O(n³)
LC 11	Container With Most Water	Opposite-end	Move shorter side
LC 42	Trapping Rain Water	Opposite-end	Track running maxes
LC 26	Remove Duplicates Sorted Array	Partition	In place
LC 27	Remove Element	Partition	In place
LC 80	Remove Duplicates II (≤2 each)	Partition	Allow 2
LC 283	Move Zeroes	Partition	Stable
LC 75	Sort Colors (Dutch Flag)	Three-way partition	Dijkstra 1976
LC 88	Merge Sorted Array	Two-array two-pointer	In-place from end
LC 125	Valid Palindrome	Opposite-end	Skip non-alphanumeric
LC 344	Reverse String	Opposite-end	Trivial
LC 345	Reverse Vowels	Opposite-end	Conditional swap
LC 977	Squares of Sorted Array	Opposite-end → write into result	Negative numbers go large too
LC 141	Linked List Cycle	Fast/slow	See Linked List Cycle Detection
LC 142	Linked List Cycle II	Fast/slow + restart trick	Floyd’s full algorithm
LC 876	Middle of Linked List	Fast/slow	Single pass
LC 19	Remove Nth from End	Fast/slow with k-offset	One pass
LC 234	Palindrome Linked List	Fast/slow + reverse second half	O(1) extra
LC 287	Find Duplicate Number	Floyd cycle on index map	Clever transform
LC 905	Sort Array By Parity	Partition	Two-way
LC 922	Sort Array By Parity II	Two pointers (even/odd offsets)
LC 581	Shortest Unsorted Continuous Subarray	Two pointers (boundary scan)
LC 524	Longest Word in Dictionary via Deleting	Two-string two-pointer

11. Open Questions

• Is there a clean characterization of the exact class of problems where two pointers strictly beats hash tables, beyond “sorted input + space-constrained”? Conjectured: problems where the predicate is monotone jointly in the two indices.
• How does the two-pointer pattern generalize to k > 2 for problems other than k-Sum? The recursive reduction is well known; iterative k-pointer schemes are not.
• When does same-direction two-pointers turn into Sliding Window vs. stay distinct? The boundary is fuzzy; both have a left and a right advancing rightward. The distinguishing feature seems to be whether the window’s contents are state (sliding window) or whether the pointers are independent cursors (two pointers proper).

12. See Also

• Sliding Window — same-direction two-pointers with window-state semantics
• Linked List Cycle Detection — Floyd’s tortoise-and-hare, the canonical fast/slow application
• Hash Table — the alternative when the array is unsorted and extra space is allowed
• Binary Search — another O(log n) prune-the-search-space technique; sometimes interchangeable with two pointers on monotone problems
• Quicksort — Lomuto and Hoare partition schemes are partition-pointer variants
• Merge Sort — the merge step is a two-array two-pointer walk
• Big-O Notation — for the O(n) vs O(n²) justification
• SWE Interview Preparation MOC