Two pointers

Try it: Two Sum II, step by step

Drag through the canonical sorted-input pair-sum problem. Watch the pointers move under the invariant: sum < target → L right; sum > target → R left.

1 · Why two pointers matters

Two pointers is the cheapest way to turn an O(n²) brute force into O(n). The mechanism. Monotone invariant on a sorted (or structurally monotone) input. Lets each pointer move at most n steps in one direction, never revisits a position. Total work is linear by amortised counting — there's no clever data structure, no hash, no recursion. Just two indices and a comparison.

• The trade. O(n) time and O(1) extra space. This combination is rare; hash map and binary search beat brute force on time but pay O(n) or O(log n) space. Two pointers is the only O(n)-time + O(1)-space tool for many shapes.
• The precondition. Some structure that makes "ruling out one side" safe. Usually sortedness; sometimes a different monotonicity (heights in container-with-most-water; counts of letters in a window).
• The proof. At each step, we eliminate one element from consideration. After n steps, we've eliminated all of them — so we either found the answer or it doesn't exist. The argument is shorter than the algorithm.
• What it can't do. Problems that require comparing arbitrary pairs (not just L and R under a monotone rule). Problems where the input isn't sorted and sorting destroys index information you need. Problems with non-monotone validity predicates (some sliding-window variants).

2 · How to recognise it: five distinct shapes

Two pointers takes five recognisable shapes. Naming the shape upfront makes the rest of the solve mechanical.

Shape A: opposite ends converging

L at index 0, R at index n−1; they walk toward each other under some monotone rule. Two Sum II (LC 167), Valid Palindrome (LC 125), Container With Most Water (LC 11), Trapping Rain Water (LC 42). The loop condition is l < r; each iteration moves at least one pointer; total iterations ≤ n.

Shape B: fast / slow on a linked list or array

Both pointers start at the same end; one moves faster (twice as fast, or one waits for a condition). Floyd's cycle detection (LC 141, 142), Find the Middle (LC 876), Find the Duplicate Number (LC 287). The fast pointer's role is "scout"; the slow pointer's role is "anchor" or "position to return".

Shape C: partition / Dutch national flag

Pointers mark region boundaries; elements get swapped into the right region as the scanner advances. In-place dedupe (LC 26), Move Zeros (LC 283), Sort Colors / Dutch Flag (LC 75), partition step of quicksort. The "writer" pointer trails the "scanner"; values get committed to a region only when the predicate matches.

Shape D: merge two sorted

One pointer per input array, plus an output pointer. At each step, pick the smaller (or appropriate) element and advance its pointer. Merge Two Sorted Lists (LC 21), Merge Sorted Array (LC 88), the merge step of merge sort. Linear in total length, no extra space if the destination is pre-allocated (LC 88 with merge-from-the-back).

Shape E: sorted-array pair / triple sum

Special case of opposite-ends where the sum (or product) is the comparison. Two Sum II is the canonical. 3Sum and 4Sum extend with outer loops. The dedupe wrinkle, skipping equal values when advancing, is the most common bug.

3 · Canonical example: Two Sum II (LC 167)

Problem. Given a sorted array and a target, return the indices (1-based) of two numbers that sum to the target. Each input has exactly one solution; you may not use the same element twice. O(1) extra space required.

Input:  numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]
Explanation: 2 + 7 = 9 → indices 1 and 2 (1-based).

Why two pointers

• Brute force is O(n²): try every pair.
• Hash map is O(n) time, O(n) space, but the problem says O(1) space.
• Sortedness gives us monotonicity. Two pointers from opposite ends gives O(n) time, O(1) space.

The invariant, in plain words

At every step, the answer (if it exists) lies in [L, R]. We never "skip past" the answer because:

• If a[L] + a[R] < target: every pair using a[L] is too small (because all a[R'] ≤ a[R] for R' ≤ R). So a[L] can't be in the answer; advance L.
• If a[L] + a[R] > target: every pair using a[R] is too big (because all a[L'] ≥ a[L] for L' ≥ L). So a[R] can't be in the answer; retreat R.
• If a[L] + a[R] == target: found.

Build the intuition: answer this before you code

• What's the invariant? Articulate it: at every step, the answer (if it exists) lies in [L, R]. Why?
• When a[L] + a[R] < target, which pointer must move and why? Hint: which side has values you've ruled out?
• When a[L] + a[R] > target, which pointer must move and why?
• What's the loop termination condition? L < R or L ≤ R? Test on a 2-element input.
• How do you guarantee O(n)? How many times can each pointer move? In which direction?

Go scaffold: fill in the TODOs

// twoSumSorted returns 1-based indices of the pair summing to target.
// Precondition: numbers is sorted ascending; exactly one solution exists.
func twoSumSorted(numbers []int, target int) []int {
    l, r := 0, len(numbers)-1

    for l < r {
        // TODO: compute the current sum
        // TODO: if sum equals target, return the 1-based pair
        // TODO: if sum is too small, advance the correct pointer
        // TODO: if sum is too large, advance the correct pointer
    }

    return nil // unreachable per the problem statement
}

4 · Five-problem progression

Solve in order. Each step builds on the previous; don't skip. Time-box each at 25 minutes; if stuck past 20, peek at the pattern hint only.

5 · Same-direction variant: fast / slow pointers

The other half of the pattern. Both pointers start on the left; one moves faster than the other, or one waits for a condition.

Use cases

• In-place dedupe on a sorted array (LC 26). slow writes; fast scans.
• Move zeros to end / partition (LC 283). slow tracks the boundary; fast finds the next non-zero.
• Cycle detection in a linked list (LC 141, Floyd's). slow moves 1, fast moves 2; if they meet, there's a cycle.
• Find the middle of a linked list (LC 876). fast reaches the end when slow is at the middle.

Build the intuition: in-place dedupe

• Two roles for the pointers. One pointer is a writer; the other is a scanner. Which is which?
• What invariant does the writer maintain? All positions [0..writer] hold unique values seen so far. The scanner explores ahead.
• When does the writer advance? Only when the scanner finds a value different from nums[writer].
• When does the scanner advance? Every iteration — that's how it covers the input.
• What does the function return? Length of the unique-prefix, not the array itself.

Go scaffold: in-place dedupe

// removeDuplicates compacts duplicates in a sorted slice in-place.
// Returns the length of the unique-value prefix.
func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    slow := 0
    for fast := 1; fast < len(nums); fast++ {
        // TODO: when does slow need to advance?
        // TODO: when slow advances, what do you write at nums[slow]?
    }

    return slow + 1
}

6 · Floyd's tortoise & hare: see the cycle form

The same-direction-pointers idea has a beautiful application in linked lists: Floyd's cycle-detection algorithm, also called the tortoise and hare. One pointer moves one step at a time; the other moves two. If the list is acyclic, the fast pointer hits null. If there's a cycle, the fast pointer is doomed to overlap the slow one — and once you know that, a second pass finds the cycle's entry point.

The two-phase argument

Phase one, detect: slow advances 1, fast advances 2. After k steps, the gap (along the cycle) shrinks by 1 each step modulo cycle length. Inside the cycle they must meet within cycle_length further steps.

Phase two, find the entry: number-theoretically, the distance from the head to the entry equals the distance from the meeting point around the loop back to the entry. So reset slow to head, advance both one step at a time, and they meet exactly at the entry. Two pointers, O(n) time, O(1) space — no extra hash set.

Go scaffold: two-phase Floyd's

type ListNode struct {
    Val  int
    Next *ListNode
}

// detectCycle returns the node where the cycle begins, or nil.
func detectCycle(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }

    // PHASE 1 — race until they meet (cycle) or fast hits nil (no cycle)
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        // TODO: detect the meeting condition
    }
    // TODO: handle the "no cycle" case — when does the loop exit cleanly?
    if /* TODO: condition for no cycle */ {
        return nil
    }

    // PHASE 2 — reset slow to head, advance both ×1
    slow = head
    for slow != fast {
        // TODO: advance both pointers by 1
    }
    return slow
}

Where Floyd's appears in disguise

• LC 141: Linked List Cycle. The canonical detection problem.
• LC 142: Linked List Cycle II. The "find the entry" extension. Both phases of the algorithm.
• LC 287: Find the Duplicate Number. Treat nums as an implicit linked list where i → nums[i]. The duplicate value forces a cycle; Floyd's finds it in O(1) extra space.
• LC 202: Happy Number. Cycle detection on the squared-digit transformation. Either Floyd's or a hash set.
• LC 876: Middle of the Linked List. Slow/fast where fast goes 2×; when fast hits the end, slow is at the middle. The simplest application.

7 · 3Sum walked end-to-end (LC 15)

3Sum is the classic compound use of two pointers: an outer loop fixes one element, an inner two-pointer sweep finds pairs that sum to the negation. The complexity goes from O(n³) brute force to O(n²) — and most of the cleverness is in the dedupe.

Build the intuition: answer first

• Why sort first? What does sortedness unlock? (Hint: this turns 3Sum into "for each i, do Two Sum on the rest".)
• What's the target for the inner two-pointer sweep? If we fix nums[i], what must nums[l] + nums[r] equal?
• The dedupe puzzle: there are three places. Identify each:
  1. After picking nums[i], when do we skip a duplicate first element?
  2. After finding a triple, what should L and R do about adjacent duplicate values?
  3. What's the early-termination once nums[i] > 0 and why?
• What test inputs will catch dedupe bugs? Try [0,0,0,0], [-2,-1,-1,0,1,1,2], [1,1,1].

Go scaffold: three-place dedupe

import "sort"

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    var out [][]int
    n := len(nums)

    for i := 0; i < n-2; i++ {
        // PLACE 1 — skip duplicate first elements
        // TODO: if nums[i] equals nums[i-1] (and i > 0), continue

        // EARLY TERMINATION
        // TODO: once nums[i] > 0, no triple can sum to 0 — break

        target := -nums[i]
        l, r := i+1, n-1
        for l < r {
            s := nums[l] + nums[r]
            switch {
            case s == target:
                out = append(out, []int{nums[i], nums[l], nums[r]})
                // PLACE 2 & 3 — skip duplicate L and R values
                // TODO: walk l forward while nums[l] == nums[l+1]
                // TODO: walk r backward while nums[r] == nums[r-1]
                // TODO: advance both by one final step
            case s < target:
                // TODO: advance the correct pointer
            case s > target:
                // TODO: advance the correct pointer
            }
        }
    }

    return out
}

Trace through [-4, -1, -1, 0, 1, 2]

Reference solution: the complete dedupe-correct version

import "sort"

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    var out [][]int
    n := len(nums)

    for i := 0; i < n-2; i++ {
        if nums[i] > 0 {
            break                        // smallest > 0 → no triple sums to 0
        }
        if i > 0 && nums[i] == nums[i-1] {
            continue                     // skip duplicate first element
        }

        target := -nums[i]
        l, r := i+1, n-1
        for l < r {
            s := nums[l] + nums[r]
            switch {
            case s == target:
                out = append(out, []int{nums[i], nums[l], nums[r]})
                // skip duplicate left and right
                for l < r && nums[l] == nums[l+1] {
                    l++
                }
                for l < r && nums[r] == nums[r-1] {
                    r--
                }
                l++
                r--
            case s < target:
                l++
            case s > target:
                r--
            }
        }
    }
    return out
}

Generalising to 4Sum (LC 18)

4Sum follows the same recipe: sort, fix two outer indices in nested loops, run two-pointer on the rest. Complexity O(n³). Same dedupe puzzle, now at five places (two outer levels plus two inner). Beyond 4Sum, the pattern hits diminishing returns — for k-Sum with large k, meet-in-the-middle (split into halves, hash-map the pair sums) wins at O(n^(k/2)).

8 · Dutch national flag walked end-to-end (LC 75)

LC 75 Sort Colors is the canonical three-pointer partition problem. Given an array of 0s, 1s, and 2s, sort in-place in O(n) and O(1) extra space. The trick is three pointers that carve the array into four regions: a settled 0-region, a settled 1-region, an unprocessed middle, and a settled 2-region.

Problem. Sort an array of integers from {0, 1, 2} in-place. Don't use a comparison sort. Don't make two passes.

Input:  [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]

The three-region invariant

Maintain three pointers low, mid, high. At all times:

• nums[0..low−1] is all 0s, settled.
• nums[low..mid−1] is all 1s, settled.
• nums[mid..high] is unprocessed; could be anything.
• nums[high+1..n−1] is all 2s, settled.

Each step inspects nums[mid] and either swaps it toward the appropriate region, advancing the relevant pointer. The loop ends when mid > high — the unprocessed region is empty.

Build the intuition: the three branches

• If nums[mid] == 0: swap with nums[low], advance both low and mid. (The swapped-in value was a settled 1, so we can safely advance past it.)
• If nums[mid] == 1: already in the right region; just advance mid.
• If nums[mid] == 2: swap with nums[high], decrement high. Do not advance mid: the swapped-in value is unprocessed and must be re-examined.

Diagram: partitioning into three regions

Go scaffold: fill in the three branches

func sortColors(nums []int) {
    low, mid, high := 0, 0, len(nums)-1
    for mid <= high {
        switch nums[mid] {
        case 0:
            // TODO: swap nums[low] and nums[mid]; advance both low and mid
        case 1:
            // TODO: advance only mid
        case 2:
            // TODO: swap nums[mid] and nums[high]; decrement high (do NOT advance mid)
        }
    }
}

Trace through [2, 0, 2, 1, 1, 0]

9 · Trapping rain water: two-pointer with a twist (LC 42)

LC 42 is the hardest classic two-pointers problem. The setup: an array of bar heights; how much water can be trapped after rain? The brute force is O(n) for each cell (find the max bar to the left and right), giving O(n²). The two-pointer solution drops it to O(n) with O(1) space.

The insight

At any cell i, the water level is determined by min(leftMax, rightMax) - height[i]. The two-pointer trick: whichever side has the smaller max bound, we know the water level there — the other side won't make it smaller. So we can commit to the lower side and move that pointer inward.

Build the intuition: three big questions

• What determines the water above cell i? Two bars trap water: the left max and the right max. The water level is min(leftMax, rightMax); the trapped amount is min(leftMax, rightMax) − height[i].
• Why don't we need full prefix-max arrays? Move the pointer on the shorter side. If height[l] < height[r], then rightMax ≥ height[r] > height[l], so the binding constraint on the left is leftMax alone — you can finalise that cell now.
• Why "shorter side moves"? The taller side is the upper bound on water for everything past the shorter one. Until we move past it, the shorter side's water level is locked.
• Two ways to track leftMax. Either (a) update leftMax = max(leftMax, height[l]) then add leftMax − height[l]; or (b) check if height[l] is the new max and skip the add. Both work; one is one branch shorter.

Go scaffold: fill in the side branches

func trap(height []int) int {
    l, r := 0, len(height)-1
    leftMax, rightMax := 0, 0
    water := 0

    for l < r {
        if height[l] < height[r] {
            // The right side is taller — left's water level is bounded
            // by leftMax. Either height[l] is a new leftMax (no water here)
            // or it's lower (water = leftMax - height[l]).
            // TODO: update leftMax or accumulate water
            // TODO: advance l
        } else {
            // Symmetric for the right side
            // TODO: update rightMax or accumulate water
            // TODO: advance r
        }
    }

    return water
}

Why this beats prefix arrays

The "obvious" O(n)-time solution precomputes leftMax[i] and rightMax[i] arrays, costing O(n) time and O(n) space. The two-pointer version drops the space to O(1) by realising you don't need the full prefix-max arrays. You only need to know which side currently has the binding constraint, and that's determined by which pointer's height is smaller. The lower side cannot be raised by anything the other side does later, so we can finalise it now.

Reference solution: the complete two-pointer trap

func trap(height []int) int {
    if len(height) == 0 {
        return 0
    }
    l, r := 0, len(height)-1
    leftMax, rightMax := 0, 0
    water := 0

    for l < r {
        if height[l] < height[r] {
            // left side is shorter — left is bound by leftMax
            if height[l] >= leftMax {
                leftMax = height[l]      // new left max; no water above l
            } else {
                water += leftMax - height[l]
            }
            l++
        } else {
            // right side is shorter (or equal) — right is bound by rightMax
            if height[r] >= rightMax {
                rightMax = height[r]
            } else {
                water += rightMax - height[r]
            }
            r--
        }
    }
    return water
}

Trace through [0,1,0,2,1,0,1,3,2,1,2,1]

Two-pointer vs monotonic stack

The monotonic stack version processes the array left to right, maintaining a stack of decreasing heights. When a higher bar is encountered, it pops shorter bars off the stack and computes the water trapped between the new bar and the previous taller bar. Linear time, O(n) worst-case space (stack can hold the whole array on monotonically decreasing input). The two-pointer version is the same O(n) time with O(1) space; both are valid.

// Monotonic stack alternative — clear but uses O(n) space.
func trapStack(height []int) int {
    stack := []int{}
    water := 0
    for i, h := range height {
        for len(stack) > 0 && height[stack[len(stack)-1]] < h {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if len(stack) == 0 {
                break
            }
            left := stack[len(stack)-1]
            width := i - left - 1
            bounded := min(height[left], h) - height[top]
            water += width * bounded
        }
        stack = append(stack, i)
    }
    return water
}

9b · Bonus: Merge Sorted Array in-place (LC 88)

LC 88 demonstrates shape D, merge two sorted, plus a twist that tests whether you've actually internalised the two-pointer mechanics. The naive merge walks the inputs left-to-right and writes into a buffer. LC 88 disallows the buffer; the destination array nums1 has trailing slots reserved for nums2's elements.

Problem. Given two sorted arrays nums1 (length m + n, with the first m slots populated and the last n empty) and nums2 (length n), merge nums2 into nums1 in sorted order. In-place.

The merge-from-the-back trick

Walking forward, every write into nums1 would clobber a value we haven't yet processed. Walking backward, starting from the last slot of nums1, every write lands in already-reserved space. The two read pointers walk backward from the ends of the populated portions; the write pointer walks backward from the end of nums1.

Go implementation

func merge(nums1 []int, m int, nums2 []int, n int) {
    i := m - 1                           // last populated index of nums1
    j := n - 1                           // last index of nums2
    k := m + n - 1                       // write position at end of nums1

    for i >= 0 && j >= 0 {
        if nums1[i] > nums2[j] {
            nums1[k] = nums1[i]
            i--
        } else {
            nums1[k] = nums2[j]
            j--
        }
        k--
    }
    // If any nums2 elements remain, copy them in
    for j >= 0 {
        nums1[k] = nums2[j]
        j--
        k--
    }
    // Remaining nums1 elements are already in place — no action needed
}

10 · Sister algorithms

Two pointers belongs to a family of related techniques. Knowing the cousins helps you pick the right tool and reach beyond LC into Codeforces and operations-research territory.

Three pointers: fix one, two-pointer the rest

3Sum (LC 15) is the canonical example. Outer loop fixes nums[i]; inner two pointers find pairs summing to −nums[i]. Same dedupe pattern, one extra layer. Complexity O(n²). The pattern extends: 3Sum Closest (LC 16), 3Sum Smaller (LC 259), 3Sum with Multiplicity (LC 923).

Four pointers: 4Sum reduction

4Sum (LC 18) nests two outer loops around a two-pointer inner sweep. Complexity O(n³). For larger k (5Sum, 6Sum), the meet-in-the-middle approach (split the input in half, hash all pair sums on one side, look up complements on the other) gets down to O(n^(k/2)).

Quickselect / Hoare partition

Quicksort's partition step uses two pointers walking inward from opposite ends, swapping out-of-place elements as they meet. Quickselect re-uses the same partition to find the k-th smallest in O(n) average / O(n²) worst case. Same mechanical pattern as two-pointer; different goal. LC 215 Kth Largest is the standard quickselect interview question.

// Hoare partition — the engine inside quicksort and quickselect.
// Returns the pivot's final position.
func partition(a []int, lo, hi int) int {
    pivot := a[lo+(hi-lo)/2]
    l, r := lo-1, hi+1
    for {
        for {
            l++
            if a[l] >= pivot {
                break
            }
        }
        for {
            r--
            if a[r] <= pivot {
                break
            }
        }
        if l >= r {
            return r
        }
        a[l], a[r] = a[r], a[l]
    }
}

Sliding window: the same-direction cousin

A sliding window is two same-direction pointers (left and right) that maintain a window invariant. When the invariant breaks on the right side, the left advances until it's restored. Sister pattern; covered separately under sliding window.

Merge step of merge sort

The merge in merge sort is shape D — one pointer per input array, one output pointer. Linear in the total length, O(n) extra space for the buffer. The same skeleton appears in external sorts, polynomial multiplication, and the "merge K sorted lists" family (LC 23 is the K-way generalisation using a heap).

11 · How to solve hard two-pointer problems step-by-step

Run through the four questions in order. If any answer is unclear, slow down — the bug is in the design, not the code.

1. What is the monotone invariant? Articulate the rule "if L and R satisfy condition X, then this element can never be in the answer". Sortedness usually supplies it for free. For container-with-water and rain-water, you need to discover the invariant: the shorter side is the binding constraint. If you can't articulate the invariant, you don't have a two-pointer solve yet.
2. What moves which pointer? The comparison rule that triggers each pointer's advance. Two Sum II: sum too small → L advances; sum too big → R retreats. 3Sum: same as Two Sum, inside the outer loop. Container: shorter side advances. Rain water: shorter side advances. Always tied to "which side has an element we can rule out".
3. How are duplicates handled? The most common bug-magnet. In 3Sum, duplicates must be skipped at three places (outer i, inner L after a hit, inner R after a hit) or you return the same triple repeatedly. In sorted-array dedupe, the writer only advances when the scanner finds a new value. Most pattern variations introduce one new place duplicates have to be skipped.
4. Do you need to sort first? If the input isn't sorted, can you sort? Sorting is O(n log n), which is fine for n ≤ 10⁵; it dominates the O(n) two-pointer sweep. If sorting destroys indices you need (e.g. Two Sum returning original indices), reach for a hash map instead.

12 · Common pitfalls: what breaks

• Forgetting the loop condition is L < R, not L ≤ R. Off-by-one. With ≤ you'd compare an element to itself; the problem usually forbids that. Symmetrically, with closed intervals you want ≤; with half-open [L, R) you want <. Pick a convention and stick with it across the file.
• Closed vs open interval confusion. Binary search's "hi = mid - 1 vs hi = mid" has a two-pointer analogue. When in doubt, write down explicitly which indices are "still in play" and verify the loop condition matches.
• Assuming sortedness. If the input isn't sorted, two pointers usually doesn't apply. Sort first (O(n log n)) or reach for a hash map. Sorting destroys index information; if the caller needs original indices, decorate-sort-undecorate or use a hash map.
• Dedupe in sorted-input 3Sum. Three places to skip duplicates (outer i, inner L after a hit, inner R after a hit). Forgetting any one returns the same triple multiple times. The classic failing test case is [0,0,0,0] — without proper dedupe you get [[0,0,0], [0,0,0], ...]. Always run this test before submitting.
• The infinite loop inside dedupe walks. When skipping duplicates after a 3Sum hit (while l < r && nums[l] == nums[l+1]), the l < r guard is essential. Without it, on [0,0,0,0] the pointer walks past the right edge and crashes. Drill this in every dedupe loop.
• The wrong move on container-with-water. Move the shorter side, not the larger one — only the shorter side limits the area; moving the larger side can never improve. The intuition: the area is min(L, R) × width; moving the taller side leaves min unchanged and decreases width.
• Overflow in pair sum. If values can be near INT_MAX, a[L] + a[R] overflows. Use 64-bit, or rewrite the comparison as a[L] < target - a[R] (still risky if the subtraction underflows; in Go, use int which is 64-bit on 64-bit platforms).
• Linked-list two-pointers: null check the fast. Floyd's: check fast != nil && fast.Next != nil before fast = fast.Next.Next. Skipping the check segfaults on the odd-length, no-cycle list. The textbook bug.
• Modifying in-place but expecting the original array later. Several patterns (move-zeros, in-place dedupe, Dutch flag) destroy the input. If the caller needs it, copy first. If you can't afford the copy, document the side effect.
• Pointer wrap-around on sentinel. When a sentinel value (like Go's math.MaxInt) is used to simplify boundary cases, arithmetic on it can wrap. sentinel + 1 becomes math.MinInt. Be especially careful in the partition step of quicksort, where Hoare partition uses lo - 1 and hi + 1 as starting points; these are safe but only because of the loop structure.
• The 1-based vs 0-based indexing trap. LC 167 (Two Sum II) asks for 1-based indices in the output. Forgetting to add 1 gives wrong answers on every test case. Read the problem twice.
• Two-pointer plus hash-map confusion. Some problems want a hash map (Two Sum, unsorted input). Some want two pointers (Two Sum II, sorted input). Some want both (Minimum Window Substring, sliding window + hash map). Misclassifying wastes 10 minutes; the trigger is "is the input sorted?".
• The "wait, why does this advance?" loop bug. A common Sort Colors mistake: advancing mid on the 2-swap. The swapped-in value came from the unprocessed region — you can't classify it yet. The general rule: when a swap brings in a value from "settled" territory, advance both pointers; when it brings in a value from "unprocessed" territory, advance only the originating pointer.
• Forgetting to break early. 3Sum has a break once nums[i] > 0: no triple can sum to 0 with the smallest element positive. Forgetting it doesn't change correctness but doubles runtime on average inputs.

13 · Complexity

Two pointers is one of the few O(n) algorithms with O(1) space. That combination is the reason it shows up so often.

14 · Variants & related patterns

• Sliding window. Same-direction two pointers with a window invariant. The sister pattern.
• Binary search. When the input is sorted, also consider whether the answer space is monotone — that's a different pattern with the same precondition.
• Recursion. Merge sort uses two pointers in its merge step. Quickselect is a partition + two-pointer hybrid.
• Dutch national flag (3-way partition). Three pointers; partition into <, =, > pivot. LC 75.
• Adjacent: data structures cabinet. Reference for arrays, strings, linked lists.

15 · Where this gets asked

Two-pointer is interview-friendly because the trigger phrases are unambiguous: "sorted array", "find a pair", "in-place modify", "cycle in a list". Six companies and what they tend to reach for:

16 · Try it yourself

Five problems, ordered by depth. Spend 30 minutes on each before peeking at the hint.

Two Sum II · LC 167

The canonical opposite-ends warm-up. Sum the pair; move left up if sum is too small, right down if too big. Hint: indices are 1-based in the answer; the off-by-one bug here catches everyone once.

Valid Palindrome · LC 125

Opposite-ends with character filtering. Skip non-alphanumeric on both sides; compare lowercased. Hint: pre-cleaning the string is allowed but slower; the in-place version is the version they want.

3Sum · LC 15

Sort, then fix the first index and run two-pointer on the rest. Hint: skip duplicates at all three levels (the outer index AND both pointers), or you'll output the same triple multiple times.

Linked List Cycle II · LC 142

Floyd's tortoise & hare, then restart one pointer to find the cycle entry. Hint: the math is "distance from head to entry = distance from meeting point to entry, going forward." Memorise this proof, it shows up in interview discussions.

Stretch: Trapping Rain Water · LC 42

Opposite-ends with running max on each side. Move the smaller-max side; water at that index is bounded by that side's max. Hint: the O(n) space solution with two prefix-max arrays is easier to derive; the two-pointer version saves the space.

Further reading

• Skiena — The Algorithm Design Manual. Section 4.3 on sorting + two-pointer pair-finding. Concise.
• Sedgewick & Wayne — Algorithms (4th ed). Chapter 1.4 covers analysis of pair-finding; chapter 2.3 on quicksort partition.
• Neetcode — Two Sum II video. Five-minute walkthrough; the cleanest free explainer for the canonical example.
• Floyd — "An algorithm for constructing balanced trees" (1964). Tangential, but Floyd's cycle-detection (1967) is the foundational paper for slow/fast pointers.
• Adjacent: the problem-solving hub. Mental models, methodology, the practice rules.
• Adjacent: binary-search simulator. Same precondition (sorted), different pattern.