Two Pointer Techniques

Why Two Pointers? From Nested Loops to Linear Time

Picture the moment in an interview when you're asked to find two numbers in a list that add up to a target value. The instinctive first move — the one almost everyone reaches for — is to check every possible pair: for each element, scan the rest of the array looking for its partner. It works. It's also the kind of solution that makes an interviewer ask, "Can you do better?" That question is the entire reason this lesson exists. Why does checking every pair feel so natural, and why is it almost always a sign that a faster structure is hiding in plain sight? This section builds the foundation for answering that: the two-pointer technique, a way of walking through a sequence using two coordinated positions instead of re-scanning it over and over. We'll contrast the brute-force nested loop with a single linear pass, define precisely what "two pointers" means, and preview the two movement patterns — converging pointers and fast-slow pointers — that the rest of this lesson is built around.

The Nested-Loop Habit and Its Hidden Cost

When a problem involves finding a relationship between two elements in a collection — a pair that sums to a target, a pair that's closest to a target, two elements that satisfy some ordering constraint — the default approach is usually a nested loop: an outer loop picks the first element, and an inner loop scans everything after it looking for a match.

def has_pair_with_sum_bruteforce(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return True
    return False

This works for any array, sorted or not, and that generality is exactly its appeal — and exactly its cost. For an array of length n, the outer loop runs n times, and for each of those, the inner loop runs up to n times again. The result is O(n²) time: doubling the input size roughly quadruples the work. On an array of a few dozen elements this is invisible. On an array of tens of thousands, it's the difference between a solution that returns instantly and one that visibly grinds.

🎯 Key Principle: Nested loops over the same collection are a strong signal to ask whether the second loop is doing redundant work that a smarter traversal order could eliminate. Not every nested loop can be flattened this way, but when the inner loop is re-deriving information the outer loop already passed by, a two-pointer pass is often the fix.

What the Two-Pointer Technique Actually Means

The two-pointer technique is the practice of maintaining two positions (indices) into a sequence and advancing each one according to a rule, instead of restarting a scan from the beginning every time. Rather than the inner loop re-reading the array for every value of the outer loop, both positions move forward through the data exactly once, in a single coordinated pass. Here is that same pair-sum question solved with two index variables instead of two loops, assuming the array is sorted:

def has_pair_with_sum_two_pointer(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return True
        elif current_sum < target:
            left += 1   # sum too small, need a bigger value
        else:
            right -= 1  # sum too large, need a smaller value
    return False

Notice what changed structurally: there is no inner loop. left and right each move at most n times total across the entire run, so the work done is proportional to n, not n² — this is O(n) time. The mechanics of why moving a pointer here is safe (it depends on the array being sorted) and a full step-by-step trace belong to the next section, "The Converging Pointers Pattern" — what matters here is the shape of the change: two index variables replacing two nested loops.

💡 Mental Model: Think of the brute-force version as re-reading a book from page one every time you want to check whether two pages relate to each other. The two-pointer version is like holding one finger at the front of the book and one at the back, and sliding them toward each other based on what you find — you never flip back to a page you've already ruled out.

Two Families of Movement You'll Build On

Not every two-pointer solution moves its pointers the same way. Across the problems this technique solves, the movement almost always falls into one of two broad families — useful as a starting map of the territory, though, like any two-category split, some problems will stretch or combine them rather than fitting one bucket cleanly.

Converging pointers (opposite ends closing in):
  left  = 0
  right = n - 1
  ↓ compare nums[left] and nums[right] against a target condition
  ↓ move left forward OR move right backward, never both blindly
  ↓ repeat until left meets or crosses right

Fast-slow pointers (same direction, different speed or role):
  slow = 0
  fast = 0
  ↓ fast advances every step (sometimes two steps at a time)
  ↓ slow advances only when a condition holds, or lags a fixed distance behind
  ↓ repeat until fast reaches the end (or the two meet, for cycle detection)

The first family, converging pointers, starts one pointer at each end of a sequence and closes the gap between them based on a comparison — the pair-sum sketch above is an instance of it. The second family, fast-slow pointers, keeps both pointers moving in the same direction but gives them different jobs: one might scan ahead as a "reader" while the other lags behind as a "writer," or one might move twice as fast as the other to detect a loop. A minimal sketch of that reader/writer shape looks like this:

## Illustrative shape only — a full in-place compaction
## walkthrough belongs to a later, dedicated lesson.
slow = 0
for fast in range(len(nums)):
    if keep_condition(nums[fast]):
        nums[slow] = nums[fast]
        slow += 1

Both families achieve the same underlying goal — replacing repeated re-scanning with a single coordinated pass — but the rule for advancing the pointers differs enough that they're worth treating as distinct patterns. The next two sections, "The Converging Pointers Pattern" and "The Fast-Slow (Same-Direction) Pointers Pattern," each take one of these families and go deep: worked traces, correctness preconditions, and the specific bugs each one invites.

🤔 Did you know? The "two-pointer" label is really a family name for a traversal strategy, not a single algorithm — which is part of why it shows up across such different-looking problems. The same underlying discipline of "advance a position based on a rule instead of restarting" is what a converging-pointer pair-sum solution and a fast-slow cycle detector both have in common, even though their code looks quite different.

Where the Named Problems Fit

You'll likely already know some of the classic problems associated with this technique by name: checking whether a string is a palindrome, finding the container that holds the most water between two walls, or removing duplicates from a sorted array in place. Each of these gets its own dedicated lesson elsewhere in this roadmap, with a full problem statement, worked trace, and edge-case discussion. This lesson references them only as landmarks — recognizable examples you can anchor the two families to — rather than working through them here. What this section and the two pattern sections that follow give you is the underlying mechanism those dedicated lessons all lean on.

Why This Removes an Entire Loop's Worth of Work

It's worth being precise about why this matters beyond a satisfying complexity number. In an inner loop that re-scans the remaining array for every outer-loop iteration, the inner loop is frequently re-deriving something the outer loop already knows: which values are too small, which are too large, or which region of the array can no longer contain an answer. A single pass with two coordinated pointers captures that information in the pointers' positions themselves, so no work is repeated. Concretely, the brute-force pair-sum function above performs on the order of n² comparisons, while the two-pointer version performs on the order of n — for an input with ten thousand elements, that's the difference between roughly one hundred million comparisons and roughly ten thousand.

This is also precisely the shape that interview-style array and string questions tend to reward: a problem that looks like it needs two nested loops, but where sorting, a monotonic property, or a simple forward/backward relationship lets one of those loops disappear entirely. Spotting that opportunity — recognizing when an inner loop is redundant rather than essential — is the skill this lesson builds toward, one pattern at a time.

The Converging Pointers Pattern

The most common shape the two-pointer technique takes is a pair of indices that start at opposite ends of a sequence and walk toward each other until they meet. This is the converging pointers pattern (also called the opposite-ends or left-right pointer pattern), and it is the workhorse behind a huge class of problems where you need to find a pair of elements satisfying some relationship — a target sum, a target difference, or an ordering constraint.

Pattern Mechanics

The setup is always the same: one pointer, conventionally called left, starts at index 0; the other, right, starts at the last valid index. On each iteration you evaluate some condition using the values at left and right, and that comparison tells you which pointer to move inward. The loop continues until left and right cross or meet, at which point every possible pair has effectively been considered exactly once.

left = 0                              right = n - 1
  ↓                                        ↓
[ a0, a1, a2, a3, a4, a5, a6, a7, a8, a9 ]
  → as the loop runs, left moves right and right moves left,
    the gap between them shrinking on every step

What makes this different from just nesting two loops is that each step discards a whole range of candidates at once, not just one. When you move left forward, you're not just skipping one comparison — you're declaring that left's old position can never form a valid pair with anything to its right, for every remaining value of right. That's the source of the linear-time guarantee, and it only holds because of a precondition we'll come back to shortly.

Worked Example: Pair Sum in a Sorted Array

Consider the sorted array [2, 7, 11, 15, 18, 24, 30] and a target sum of 33. We want to find the indices of two numbers that add up exactly to the target.

Start with left = 0 (value 2) and right = 6 (value 30). At each step we compute nums[left] + nums[right] and compare it to the target:

• Step 1: left=0 (value 2), right=6 (value 30). Sum = 32, which is less than 33. The sum is too small, and since the array is sorted, the only way to increase the sum is to bring in a larger left-hand value — so we advance left.
• Step 2: left=1 (value 7), right=6 (value 30). Sum = 37, which is greater than 33. The sum is too large, so we shrink right to bring in a smaller value.
• Step 3: left=1 (value 7), right=5 (value 24). Sum = 31, too small — advance left.
• Step 4: left=2 (value 11), right=5 (value 24). Sum = 35, too large — decrement right.
• Step 5: left=2 (value 11), right=4 (value 18). Sum = 29, too small — advance left.
• Step 6: left=3 (value 15), right=4 (value 18). Sum = 33 — a match. The pair (15, 18) at indices (3, 4) is returned.

Notice that the pointers never revisited a pair and never needed to look at every combination — six comparisons solved a problem that a brute-force nested loop would have approached with up to 21 pair checks on this seven-element array. Here's the implementation that produced this trace:

def two_sum_sorted(nums, target):
    """Find indices of two numbers in a sorted list that sum to target.
    Returns a tuple of indices, or None if no pair exists.
    """
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return (left, right)
        elif current_sum < target:
            left += 1   # sum too small: only a bigger left value can help
        else:
            right -= 1  # sum too large: only a smaller right value can help
    return None

Running two_sum_sorted([2, 7, 11, 15, 18, 24, 30], 33) walks through exactly the six steps traced above and returns (3, 4).

Complexity: Three Approaches Compared

The reason converging pointers is worth learning as a distinct pattern rather than just "a clever loop" is the complexity it unlocks compared to the two approaches you'd otherwise reach for. Given the same sorted-array pair-sum problem, here's how the three strategies stack up:

Approach	⏱️ Time	💾 Space	🔒 Requires Sorted Input
🔁 Brute-force nested loop	O(n²)	O(1)	❌ No
🗂️ Hash-map lookup	O(n)	O(n)	❌ No
👉👈 Converging pointers	O(n)	O(1)	✅ Yes

The brute-force version checks every pair explicitly:

def two_sum_brute_force(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return (i, j)
    return None

Each of the n outer iterations scans up to n remaining elements, giving the familiar O(n²) blowup — on an array of a few thousand elements this is already millions of comparisons, whereas converging pointers would need only a few thousand.

The hash-map version trades space for the ability to work on unsorted data:

def two_sum_hash_map(nums, target):
    seen = {}  # maps value -> index already visited
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return (seen[complement], i)
        seen[num] = i
    return None

This is also linear time, and it doesn't care whether nums is sorted, which makes it the more general tool. But it pays for that generality with O(n) auxiliary space for the dictionary. Converging pointers matches its O(n) time while using only O(1) extra space — two integer indices, nothing more — which is the entire appeal of the pattern when the input happens to already be sorted, or when memory is constrained. If the array isn't sorted and you're not permitted to sort it first, the hash-map approach is the right fallback; the trade-off between paying to sort versus paying in space is explored further in "Harder Variants: Multi-Pointer and Sort-First Problems."

Why Sortedness Is a Precondition, Not a Nice-to-Have

The linear-time guarantee is not free — it rests entirely on one structural fact about the data: the array must be sorted, or otherwise have a monotonic property, meaning that moving a pointer in one direction produces a predictable, one-directional change in the value being compared. This is what lets you say, with certainty, "the sum at (left, right) was too small, so no pairing of the current left value with anything at or beyond right can ever reach the target" — a claim that is only true because increasing left strictly increases (or at least never decreases) the smaller half of the sum, and decreasing right strictly decreases the larger half.

If the array is unsorted, that logical elimination breaks down: advancing left past its current position could skip over a value that, paired with the current right, actually hits the target. The pointer movement would still run to completion and return some answer, but there's no guarantee it's the correct one — a subtle bug that produces plausible-looking wrong output rather than a crash. This exact misapplication is common enough to warrant its own treatment in "Common Pitfalls When Implementing Two-Pointer Solutions," but the takeaway for now is simple: before reaching for converging pointers, confirm the monotonic structure exists, either because the input is already sorted or because you sort it as a first step.

When to Reach for This Pattern

🎯 Key Principle: Converging pointers is the right tool when two conditions both hold: the data is sorted (or can cheaply be made so), and the goal involves finding a pair — or checking a relationship between two elements — tied to an order or sum condition. Classic signals include phrases like "two numbers that sum to," "pair with the smallest/largest difference," or "is this sequence a palindrome" (the palindrome check, covered in its own dedicated lesson, is really converging pointers with an equality condition instead of a sum condition).

💡 Mental Model: think of left and right as two people walking toward each other along a sorted number line, each step justified by the fact that the person who's "too far in the wrong direction" is the one who moves. Once they meet or cross, every viable pairing has been examined — nothing was skipped, and nothing was checked twice.

This converging behavior is one of two core movement families in the two-pointer toolkit. The other — pointers that travel in the same direction at different speeds rather than closing a gap — is a fundamentally different mechanism, and it's the subject of "The Fast-Slow (Same-Direction) Pointers Pattern."

The Fast-Slow (Same-Direction) Pointers Pattern

The converging pattern you just learned closes a gap: two pointers start at opposite ends and march toward each other until a comparison against a target resolves the problem. This section covers a different family entirely — one where both pointers travel in the same direction, and the interesting behavior comes not from closing a gap but from controlling the relative speed or role between the two pointers. This is the pattern behind detecting cycles in a linked structure and behind rewriting an array in place without allocating a second one.

Reader and Writer: The Core Mechanic

In a fast-slow setup, both pointers advance forward through the sequence, but they play different jobs. The fast pointer (sometimes called the reader) scans ahead, either by moving multiple steps per iteration or simply by touching every element. The slow pointer either lags behind at a fixed rate — as in cycle detection — or plays the role of a writer, only advancing when the fast pointer's scan finds something worth keeping.

Think of it as two runners on the same track, both moving clockwise. One might be twice as fast as the other (a rate difference), or one might stop and start depending on what the other one sees (a conditional lag). Either way, nothing is being compared to close a numeric gap — the relationship between the pointers is purely structural.

Generic fast-slow shape:

 slow → next candidate write position
 fast → scans every element (or every other node)

 for fast moving through the sequence:
 if fast finds something the slow pointer needs:
 use it (write it, or check it against slow)
 advance slow

Worked Example: Floyd's Cycle Detection (Tortoise and Hare)

The canonical fast-slow problem is detecting whether a linked list loops back on itself instead of terminating in None. You cannot solve this by just walking the list once, because a cyclic list has no end to walk into — a naive traversal loops forever. Floyd's cycle detection algorithm (the "tortoise and hare") solves it by advancing a slow pointer one node at a time and a fast pointer two nodes at a time. If there is no cycle, the fast pointer reaches the end first. If there is a cycle, the fast pointer eventually re-enters the loop behind the slow pointer and, moving twice as fast, is guaranteed to catch up to and land exactly on the slow pointer.

class ListNode:
 def __init__(self, val):
 self.val = val
 self.next = None

def has_cycle(head):
 slow = head
 fast = head
 while fast is not None and fast.next is not None:
 slow = slow.next # tortoise: one step
 fast = fast.next.next # hare: two steps
 if slow is fast:
 return True
 return False

Trace this on a small list with a cycle: nodes A → B → C → D → E → C (E's next points back to C, forming a loop instead of ending in None).

Both pointers start at A.

• Iteration 1: slow moves to B. fast moves two steps: A → B → C, landing on C.
• Iteration 2: slow moves to C. fast moves two steps from C: C → D → E, landing on E.
• Iteration 3: slow moves to D. fast moves two steps from E: E → C → D (using the back-edge), landing on D.

At the end of iteration 3, slow and fast are both at D — the check slow is fast succeeds, and the function correctly reports a cycle. Notice that the two pointers never needed to compare values against each other or against a target; they only needed their relative speed to guarantee an eventual meeting.

🎯 Key Principle: In a fast-slow setup, the speed difference itself does the work. As long as the fast pointer gains ground on the slow one inside a bounded loop, a meeting point is mathematically guaranteed — no comparisons against external data are required.

In-Place Compaction: Slow Writer, Fast Reader

A second major use of this pattern has nothing to do with cycles — it's about rewriting a sequence in a single pass without allocating extra memory. Here, the fast pointer acts as a reader that examines every element in order, and the slow pointer acts as a writer that only advances when the fast pointer finds something worth keeping. Because the slow pointer never moves ahead of the fast one, it's always safe to overwrite the slot at slow — that position has already been read and is no longer needed in its original form.

A simple version of this shows up in a problem like moving every non-zero value in an array to the front while preserving order, without using a second array:

def move_nonzero_to_front(nums):
 slow = 0 # write pointer: next index to place a keeper
 for fast in range(len(nums)): # read pointer: scans every element
 if nums[fast] != 0:
 nums[slow] = nums[fast]
 slow += 1
 # everything after slow is now stale; overwrite it with zeros
 for i in range(slow, len(nums)):
 nums[i] = 0
 return nums

Tracing this on [0, 1, 0, 3, 12]: the reader skips index 0 (a zero), then at index 1 finds 1 and writes it to nums[0], advancing the writer to 1. It skips index 2 (a zero), then at index 3 finds 3 and writes it to nums[1], advancing the writer to 2. Finally at index 4 it finds 12 and writes it to nums[2], advancing the writer to 3. The array is now [1, 3, 12, 3, 12] with slow = 3, and the cleanup loop zeroes out everything from index 3 onward, producing [1, 3, 12, 0, 0] — all non-zero values preserved in their original relative order, compacted to the front, in a single pass with no auxiliary array.

This same slow-write/fast-read shape is exactly what powers in-place duplicate removal from a sorted array, where the condition for advancing the writer is "this value differs from the last one written" rather than "this value is non-zero." The full walkthrough of that specific problem, including how the duplicate-skipping condition is written and why it depends on the array being sorted, is covered in its own dedicated lesson later in this roadmap.

How This Differs From Converging Pointers

It's worth being explicit about the contrast with the pattern from the previous section, because both involve "two pointers into a sequence" and it's easy to conflate them. In the converging pattern, the two pointers start apart and the algorithm's entire logic is about closing the distance between them based on a comparison — each step provably eliminates a candidate because of some ordering guarantee in the data. In the fast-slow pattern, there is no gap being closed by comparison at all. The pointers either start together and diverge at a controlled rate (cycle detection), or one trails the other by an amount that depends purely on how much the reader has "used up" so far (compaction). Nothing here relies on the sequence being sorted, and no comparison between pointer positions drives the termination condition — termination comes from reaching the end of the structure or from the fast pointer catching the slow one.

Edge Case: Guarding the Fast Pointer's Lookahead

Because the fast pointer often looks more than one step ahead, every fast-slow implementation needs a bounds check that accounts for the full lookahead distance, not just the immediate next position. In the cycle-detection code above, the loop condition checks both fast is not None and fast.next is not None before computing fast.next.next — checking only fast is not None would let the code crash by calling .next on None whenever the list has an even number of reachable nodes before the cycle (or no cycle at all).

The same care applies when finding the middle node of a list, another common fast-slow use case:

def find_middle(head):
 slow = head
 fast = head
 while fast is not None and fast.next is not None:
 slow = slow.next
 fast = fast.next.next
 return slow

Tracing this on a 4-node list A → B → C → D → None: both start at A. In the first iteration, fast.next (B) is not None, so the loop runs: slow moves to B, and fast moves two steps to C. In the second iteration, fast is C and fast.next is D, still not None, so the loop runs again: slow moves to C, and fast moves two steps from C, landing on D.next, which is None. The loop condition now fails because fast is None, so the function returns slow, which is C — the second of the two middle nodes, matching the conventional definition of "middle" for even-length lists.

⚠️ Common Mistake: Writing while fast.next.next is not None as the loop guard instead of checking fast and fast.next first. If fast itself is None, evaluating fast.next throws an error immediately; the check must always verify existence at every level the lookahead touches before dereferencing it. The same principle applies to arrays: if a fast index reads arr[i + 1], the loop condition must guarantee i + 1 is still within bounds before that read happens, not after.

Harder Variants: Multi-Pointer and Sort-First Problems

The converging and fast-slow patterns you've seen so far work on pairs: two numbers, two ends of a string, two positions in an array. Many interview-style problems ask for more — triplets that satisfy a condition, or a partition into three or more categories. The good news is that the core mechanics don't change much; you're still moving pointers based on a comparison and eliminating candidates without re-scanning. What changes is how you combine the pattern with sorting, and how many pointers you coordinate at once.

Worked Example: 3Sum

The classic 3Sum problem asks you to find every unique triplet of numbers in an array that sums to zero (the same idea generalizes to any target sum). A brute-force approach checks every combination of three indices, which costs O(n^3) — for each of the roughly n choices of the first number, you again try roughly n choices for the second, and roughly n for the third.

The key insight is that if the array is sorted, fixing one element turns the remaining problem into exactly the two-number converging-pointer search you already know: find two numbers in a sorted sub-array that sum to a specific target (here, the negative of the fixed element). So the algorithm is: sort once, then for each index i treat nums[i] as fixed and run converging pointers over the remainder of the array looking for a pair that sums to -nums[i].

def three_sum(nums):
    nums.sort()
    n = len(nums)
    result = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # skip duplicate 'fixed' values to avoid repeat triplets
        if nums[i] > 0:
            break  # sorted array: a positive fixed value can never sum to zero here
        left, right = i + 1, n - 1
        target = -nums[i]
        while left < right:
            current = nums[left] + nums[right]
            if current == target:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1   # skip duplicate left values
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1  # skip duplicate right values
            elif current < target:
                left += 1   # sum too small, need a larger left value
            else:
                right -= 1  # sum too large, need a smaller right value
    return result

Trace this on nums = [-1, 0, 1, 2, -1, -4]. After sorting: [-4, -1, -1, 0, 1, 2].

• i=0, fixed value -4, target for the pair is 4. Starting at left=1 (value -1), right=5 (value 2), the sum 1 is too small, so left advances repeatedly (through values -1, 0, 1) until left and right meet without ever reaching 4. No triplet here.
• i=1, fixed value -1, target is 1. left=2 (-1), right=5 (2): sum is 1 — a match. Record (-1, -1, 2), then advance left to 3 and pull right back to 4. Now left=3 (0), right=4 (1): sum is 1 again — another match, (-1, 0, 1). Advancing further makes left and right cross, so this fixed value is done.
• i=2: nums[2] equals nums[1] (both -1), so this fixed value is skipped — using it again would just rediscover the same triplets.
• i=3, fixed value 0, target is 0: left=4 (1), right=5 (2), sum is 3, too large, so right retreats until left and right meet with no match.

The result is [[-1, -1, 2], [-1, 0, 1]] — every valid triplet, each appearing exactly once.

⚠️ Common Mistake: it's tempting to dedupe triplets by throwing them into a set after collecting all of them, but that means doing extra comparison work on every result and still risks subtle bugs if the triplet ordering isn't canonical. The inline duplicate-skipping shown above — checking nums[left] == nums[left - 1] and nums[right] == nums[right + 1] only after a match, and skipping repeated i values before entering the inner loop — solves it during the same pass at no extra asymptotic cost. (Getting this skip logic subtly wrong, e.g. skipping before checking bounds, is one of the specific bugs covered in "Common Pitfalls When Implementing Two-Pointer Solutions.")

The Sort-First Trade-off

3Sum is the clearest illustration of a trade-off worth naming explicitly: paying to sort unlocks a cheaper search structure. Sorting the array costs O(n log n). Once sorted, the outer loop over i runs O(n) times, and each of those runs an O(n) converging-pointer scan, for a total of O(n^{2) after the sort. Since O(n}2) dominates O(n log n) for large n, the overall cost is O(n^{2) — dramatically better than the O(n}3) triple loop a brute-force scan would require, and it costs only O(1) to O(log n) extra space depending on the sorting algorithm's implementation (in-place sorts on arrays are typically counted this way, though some standard library sorts use O(n) auxiliary space internally).

🎯 Key Principle: sorting is not free, but it's frequently the cheapest way to buy a monotonic structure that pointer techniques can exploit. Whenever a problem's brute force involves nested loops over unordered data, ask whether sorting first would let a pointer scan replace one of those loops.

Worked Example: Three-Pointer Partitioning

Some problems need more than two pointers operating simultaneously, not because you're comparing pairs, but because you're grouping elements into three categories in a single pass. A well-known version of this is sorting an array containing only three distinct values (commonly framed as sorting red, white, and blue elements, or 0s, 1s, and 2s) without a general-purpose sort.

The idea, often called the Dutch national flag partition, uses three pointers: low marks the boundary before which everything is confirmed to be the smallest category, high marks the boundary after which everything is confirmed to be the largest category, and mid scans forward, deciding where the current element belongs and swapping it into place.

def sort_colors(nums):
    # nums contains only the values 0, 1, and 2
    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   # the swapped-in value at mid is already known (a 1 or checked)
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1  # do NOT advance mid: the newly swapped-in value is unchecked
    return nums

Trace this on nums = [2, 0, 2, 1, 1, 0]:

• Start: low=0, mid=0, high=5. nums[mid]=2, so swap positions 0 and 5 → [0, 0, 2, 1, 1, 2], high becomes 4, mid stays at 0.
• nums[0]=0: swap with itself, low becomes 1, mid becomes 1.
• nums[1]=0: swap with itself, low becomes 2, mid becomes 2.
• nums[2]=2: swap positions 2 and 4 → [0, 0, 1, 1, 2, 2], high becomes 3, mid stays at 2.
• nums[2]=1: mid becomes 3.
• nums[3]=1: mid becomes 4.
• mid (4) now exceeds high (3), so the loop stops.

Final array: [0, 0, 1, 1, 2, 2] — correctly partitioned in a single left-to-right pass, using O(n) time and O(1) extra space, with no separate sort step at all. This is a genuine extension beyond the two-pointer pair problems: three pointers are coordinating three regions of the same array simultaneously, and the reason mid doesn't advance after a swap with high is that the newly-arrived value is unverified and must be examined on the next iteration.

⚠️ Common Mistake: advancing mid unconditionally after every swap, including the swap with high. Since the value swapped in from the high end hasn't been checked yet, skipping over it can leave a 2 stranded in the middle region — the exact bug this pattern is designed to avoid.

Worked Example: Pair Closest to a Target

A variant of the converging-pointer pair-sum search relaxes the requirement that the pair sum exactly matches the target. Instead, you want the pair whose sum is closest to the target, which requires the pointers to keep scanning and remember the best result seen so far rather than stopping at the first match.

def pair_closest_to_target(nums, target):
    nums.sort()
    left, right = 0, len(nums) - 1
    best_pair = (nums[left], nums[right])
    best_diff = abs(nums[left] + nums[right] - target)
    while left < right:
        current_sum = nums[left] + nums[right]
        diff = abs(current_sum - target)
        if diff < best_diff:
            best_diff = diff
            best_pair = (nums[left], nums[right])
        if current_sum == target:
            break  # an exact match cannot be improved on
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return best_pair, best_diff

Trace this on the sorted array [10, 22, 28, 29, 30, 40] with target = 54:

• left=0 (10), right=5 (40): sum=50, diff=4 — recorded as the best so far. Sum is below target, so left advances.
• left=1 (22), right=5 (40): sum=62, diff=8 — worse, not recorded. Sum exceeds target, so right retreats.
• left=1 (22), right=4 (30): sum=52, diff=2 — better, recorded as the new best. Sum is below target, so left advances.
• left=2 (28), right=4 (30): sum=58, diff=4 — worse. Sum exceeds target, right retreats.
• left=2 (28), right=3 (29): sum=57, diff=3 — worse. Sum exceeds target, right retreats.
• left=2, right=2: pointers meet, loop ends.

The best pair found is (22, 30) with a difference of 2 from the target — and because the pointers only ever move inward, every candidate pair with a smaller theoretical difference has provably been ruled out by the same monotonic reasoning that makes the exact-sum converging search correct, so no exhaustive check of every pair was needed. This still relies on the sorted-array precondition established in "The Converging Pointers Pattern"; running it on unsorted data would let a pointer move eliminate the wrong candidates and silently miss the true closest pair.

Comparing the Costs

Each of these variants pays a different price for its guarantees. The table below reflects the time and space costs of the specific implementations just walked through, not a general claim about every possible variation of these problems:

🔧 Variant	⏱️ Time	💾 Space	🎯 Why
3Sum	O(n^2)	O(1)–O(log n) beyond output	O(n log n) sort + O(n) outer loop × O(n) inner converging scan
Three-pointer partition	O(n)	O(1)	single pass, no sorting step required at all
Closest-pair sum	O(n log n)	O(1) beyond sort	O(n) converging scan is dominated by the O(n log n) sort

Notice that the three-pointer partition is the cheapest of the three precisely because it never needs to sort first — it produces sorted-like output as a side effect of the pointer coordination itself, which only works because the input is restricted to a small, known set of distinct values. When that restriction doesn't hold, sorting remains the more general (if costlier) way to unlock a two-pointer scan, as it does for both 3Sum and the closest-pair search. Weighing which of these you need comes down to what your problem's constraints actually guarantee: a handful of known category values favors direct partitioning, while a general numeric array favors sort-then-scan.

Common Pitfalls When Implementing Two-Pointer Solutions

Knowing the converging and fast-slow patterns conceptually is only half the battle — translating them into correct code is where most bugs actually live. The two-pointer technique looks deceptively simple: two integer indices, a comparison, an increment. But that simplicity hides several traps that produce either an infinite loop, a silently wrong answer, or a crash on inputs the author never tested. This section walks through the five bugs that show up most often in practice, reproduces each one on a concrete input so you can see the failure with your own eyes, and then shows the fix.

Mistake 1: Infinite Loops from an Incomplete Conditional ⚠️

Every iteration of a two-pointer loop must move at least one pointer, in every branch of the conditional — not just the branches you happened to think of while coding. The classic way this breaks is an if / elif chain that covers two of three possible comparison outcomes and silently does nothing on the third.

Consider this buggy attempt at finding a pair that sums to a target in a sorted array:

def two_sum_buggy(arr, target):
    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
        # BUG: no else branch — when s > target, nothing happens
    return None

Trace it on arr = [1, 2, 3, 10], target = 5. left = 0, right = 3, so s = 1 + 10 = 11, which is greater than target. The if fails, the elif fails, and there is no else — so neither pointer moves. The next iteration evaluates the exact same left and right, computes the same sum, and takes the same non-branch. The loop condition left < right never changes, so this runs forever.

The fix is to make the conditional exhaustive — every reachable branch must advance a pointer:

def two_sum_fixed(arr, target):
    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
        else:
            right -= 1   # the missing branch, now handled
    return None

💡 Pro Tip: When you write a two-pointer loop, list out every branch of your conditional on paper first and confirm each one ends in a pointer move. If a branch only returns or breaks, that's fine — but any branch that falls through to the next iteration without touching left or right is a latent infinite loop.

Mistake 2: Off-by-One Errors in the Loop Condition ⚠️

The choice between left < right and left <= right is not a style preference — it encodes whether your algorithm is allowed to compare an element against itself. Get it wrong and you don't crash, you get a plausible-looking wrong answer.

Suppose you're solving the same pair-sum problem, where a valid answer must use two distinct indices. Take arr = [2, 3, 4], target = 8. No two distinct elements in this array sum to 8 (2+3=5, 2+4=6, 3+4=7), so the correct answer is "not found." Now trace a version that mistakenly uses left <= right:

left=0 (value 2), right=2 (value 4): sum=6 < 8 → left moves to 1
left=1 (value 3), right=2 (value 4): sum=7 < 8 → left moves to 2
left=2 (value 4), right=2 (value 4): sum=8 == 8 → "found", returns [2, 2]

With left <= right, the loop keeps running once left and right land on the same index, and it happily reports that arr[2] paired with itself sums to the target — a false positive, because a real solution needs two different elements. Switching the guard to left < right stops the loop the instant the pointers meet, correctly reporting no answer.

The reverse mistake also happens: using left < right on a problem where the pointers meeting at the same index is a valid state (for example, some in-place partitioning or single-pass rearrangement problems allow left == right as the final resting position). There is no universal rule — the correct guard depends on whether your problem's definition of "a valid pair" permits reusing the same index.

🎯 Key Principle: Before writing the loop guard, answer one question explicitly — "does my algorithm ever need left and right to reference the same index?" If no, use <. If yes, use <=.

Mistake 3: Incorrect Duplicate-Skipping Logic in 3Sum ⚠️

The 3Sum pattern — sort, fix one element, converge on the rest — is covered as a worked example in "Harder Variants: Multi-Pointer and Sort-First Problems." The specific bug worth isolating here is what happens when the duplicate-skipping step is missing or miswritten, because it's one of the most common sources of wrong answers in converging-pointer code.

Here is a 3Sum implementation with no duplicate handling at all:

def three_sum_buggy(nums):
    nums.sort()
    res = []
    for i in range(len(nums)):
        left, right = i + 1, len(nums) - 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
            elif s < 0:
                left += 1
            else:
                right -= 1
    return res

Trace it on nums = [-1, -1, 0, 1] (already sorted). At i=0 (nums[0]=-1), left=1, right=3: sum = -1 + -1 + 1 = -1, so left advances to 2. Now left=2, right=3: sum = -1 + 0 + 1 = 0, a match — [-1, 0, 1] is appended, and both pointers move (left=3, right=2), ending the inner loop. At i=1, nums[1] is also -1, but the buggy code never skips repeated values of i, so it repeats the exact same inner search: left=2, right=3, sum = -1 + 0 + 1 = 0 again — [-1, 0, 1] is appended a second time. The final result is [[-1, 0, 1], [-1, 0, 1]], a duplicate triplet even though there's only one distinct answer.

The fix requires two separate skips: one for the fixed outer element, and one for the inner pointers after a match is recorded.

def three_sum_fixed(nums):
    nums.sort()
    res = []
    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # skip repeated outer values
        left, right = i + 1, len(nums) - 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 repeated left values after a match
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1  # skip repeated right values after a match
            elif s < 0:
                left += 1
            else:
                right -= 1
    return res

Running this fixed version on [-1, -1, 0, 1] now skips i=1 entirely (since nums[1] == nums[0]), leaving only the single correct triplet [-1, 0, 1].

⚠️ Common Mistake: the inverse bug is just as damaging — skipping too aggressively. If you compare nums[i] to nums[i + 1] instead of nums[i - 1], you skip the first occurrence of a repeated value instead of the later ones, which can eliminate the only triplet where that value participates and cause valid answers to vanish rather than duplicate. Always compare against the previous index you've already processed, never the next one you haven't visited yet.

Mistake 4: Converging Pointers on Unsorted Input ⚠️

The converging-pointer pattern's correctness proof relies entirely on the array being sorted (or monotonic in some sense) — that precondition is established in "The Converging Pointers Pattern." The pitfall worth calling out here is how quietly this fails: there's no crash, no exception, just a wrong boolean or a missed pair.

def has_pair_with_sum(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return True
        elif s < target:
            left += 1
        else:
            right -= 1
    return False

Run this on the unsorted array arr = [3, 5, 1, 9] looking for target = 10. A valid pair exists: 1 + 9 = 10. Trace it: left=0 (3), right=3 (9), sum =12 > 10 → right moves to 2. left=0 (3), right=2 (1), sum =4 < 10 → left moves to 1. left=1 (5), right=2 (1), sum =6 < 10 → left moves to 2. Now left == right, the loop ends, and the function returns False — even though 1 and 9 sum to exactly 10. The bug isn't in the pointer logic at all; it's that moving left forward or right backward only eliminates candidates when the array's order guarantees that the sum changes monotonically in the direction you moved. On unsorted data, that guarantee doesn't hold, so the elimination step is invalid and the algorithm can walk right past a real answer without ever detecting it.

The fix is to sort first, accepting the added O(n log n) cost discussed in "Harder Variants," and to keep track of original indices separately if the problem asks for positions rather than values:

def has_pair_with_sum_sorted(arr, target):
    arr = sorted(arr)  # sorting restores the monotonic property the pattern needs
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return True
        elif s < target:
            left += 1
        else:
            right -= 1
    return False

Mistake 5: Skipping Edge Cases Before the Loop Starts ⚠️

The last recurring failure has nothing to do with the pointer movement itself — it's what happens before the loop even runs. Three inputs deserve an explicit check every time you write a two-pointer function:

• Empty array: if left = 0 and right = len(arr) - 1 = -1, most left < right guards correctly skip the loop body entirely, but code that touches arr[0] or arr[right] before the loop (for example, to initialize a running best value) will throw an index error.
• Single element: left = right = 0 means the loop body never executes under a strict < guard, which is usually correct for pair-finding problems — but if your problem's definition allows a single element to be a trivial answer, you need to handle that case explicitly, since the loop will never touch it.
• All-equal elements: an array like [4, 4, 4, 4] is where duplicate-skip logic (Mistake 3) most often reveals a bounds bug — a while nums[left] == nums[left - 1]: left += 1 skip loop with no left < right guard can walk left past right entirely, and a subsequent comparison then reads a stale or out-of-range value.

A defensive habit that costs almost nothing is to guard the entry point explicitly:

def two_sum_safe(arr, target):
    if len(arr) < 2:
        return None  # not enough elements to form any pair
    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
        else:
            right -= 1
    return None

💡 Remember: none of these five bugs are exotic — they come from the same handful of assumptions (every branch moves a pointer, the meeting condition matches the problem's semantics, duplicate skips compare against the right neighbor, the data is actually sorted, and the array has at least the elements your logic assumes). Checking these five things against your code before you consider it done catches the overwhelming majority of two-pointer bugs you'll encounter.

Summary and a Decision Framework for Choosing a Pattern

By this point you've seen two distinct ways of moving two pointers through a sequence, and you've watched each one solve problems that would otherwise cost a nested loop. The hard part in practice isn't executing either pattern once you know which one applies — it's recognizing, from a fresh problem statement, which pattern you're even looking at. This closing section turns the two patterns into a decision procedure you can run in your head within the first thirty seconds of reading a new problem.

Recap: Two Patterns, Two Different Jobs

The converging pointers pattern, covered in "The Converging Pointers Pattern," starts one pointer at index 0 and one at the last index and moves them toward each other based on a comparison against a target condition. It depends entirely on the data being sorted (or having some other monotonic structure), because that ordering is what lets you prove a candidate can be discarded when you move a pointer inward. Its natural habitat is problems phrased around pairs, sums, or ordered relationships — "find two numbers that add up to X," "find the pair with the largest gap," "find the closest sum to a target."

The fast-slow pointers pattern, covered in "The Fast-Slow (Same-Direction) Pointers Pattern," moves both pointers in the same direction but at different rates or with different roles — one reads ahead while the other writes or lags behind. There's no sortedness requirement and no "gap being closed by comparison"; instead, the correctness argument rests on the relative speed or offset between the two pointers. This pattern shows up whenever you need to compact or rewrite a sequence in place, or whenever you're trying to detect a cycle by seeing whether a faster-moving pointer ever catches up to a slower one.

It helps to see the two mechanics side by side, since the contrast is really the whole decision framework in miniature:

🔧 Aspect	🎯 Converging Pointers	🐢 Fast-Slow Pointers
🧭 Starting positions	Opposite ends (index 0 and last index)	Same starting point, or offset by a fixed lag
➡️ Direction of movement	Pointers move toward each other	Both pointers move in the same direction
📚 Data requirement	Sorted or monotonic	No ordering requirement
🔒 Correctness argument	Comparison against target eliminates candidates	Relative speed/offset guarantees the invariant
🎯 Typical goal	Pair or sum condition	In-place rewrite, or cycle detection
🛑 Stopping condition	Pointers meet or cross	Fast pointer reaches the end, or catches the slow pointer

The Decision Checklist

When you're staring at a new problem and trying to decide whether two pointers apply at all — and if so, which flavor — run through these questions roughly in order:

🧠 Is the input sorted, or can it be sorted cheaply? If yes, and the goal involves finding a pair, a sum, or some ordered relationship between two elements, that's a strong signal for converging pointers. The sortedness is what makes the "move left pointer up" or "move right pointer down" decision provably safe rather than a guess.

📚 Does the goal mention pairs, sums, or comparisons against a target value? Phrases like "two numbers that sum to," "closest pair," or "pair satisfying a condition" almost always map to converging pointers once the data is sorted, as walked through in the pair-sum example and in the closest-sum-to-target variant from "Harder Variants: Multi-Pointer and Sort-First Problems."

🔧 Does the goal involve modifying a sequence in place, one pass, without extra storage? If the task is phrased as "remove duplicates in place," "move all zeros to the end," or anything with a return value like "the new length after compaction," that's the signature of a fast-slow pair acting as reader and writer.

🔒 Does the goal involve detecting a loop or revisiting a state? If the structure is a linked list, or more generally a sequence defined by a "next" function rather than a fixed array, and the question is whether following that function loops back on itself, that's Floyd's cycle detection — a fast-slow application, not a converging one.

🎯 Is there no natural sort order and no cycle to detect, but still a pairing task? This is the edge case worth calling out explicitly: converging pointers assume monotonicity, so if the input is unsorted and can't be sorted without breaking the problem (for example, because you need to preserve original indices), a two-pointer approach may not apply cleanly at all, and a hash-map lookup is often the right fallback — as covered in "The Converging Pointers Pattern."

🎯 Key Principle: the question to ask first is never "which pointer pattern is fancier" but "what is the pointers' job — to close a gap toward a comparison target, or to maintain a controlled offset while scanning forward?" Everything else follows from that answer.

This checklist is a starting heuristic, not an exhaustive test — problems like 3Sum from "Harder Variants: Multi-Pointer and Sort-First Problems" combine a fixed outer loop with converging pointers, so the real skill is decomposing a problem into sub-parts and applying the checklist to each part rather than expecting one label to describe the whole problem at once.

Applying the Checklist to a Fresh Problem

To make the checklist concrete, consider a problem you haven't seen worked yet: given a sorted array of positive integers, determine whether there exist two indices i and j (i ≠ j) such that arr[i] * arr[j] equals a given target product. Running the checklist: the data is sorted (checklist item one satisfied), and the goal is a pair condition against a target (checklist item two satisfied). There's no in-place rewrite and no cycle to detect, so fast-slow is ruled out. That points cleanly to converging pointers, and the implementation is a direct adaptation of the sum-based version:

def has_pair_with_product(arr, target):
    """
    Determine whether two distinct elements in a sorted array
    multiply to `target`. Assumes all values are positive, so the
    product is monotonic in both pointers (mirrors the sum case).
    """
    left, right = 0, len(arr) - 1

    while left < right:
        product = arr[left] * arr[right]
        if product == target:
            return True
        elif product < target:
            left += 1   # need a larger product, move left pointer up
        else:
            right -= 1  # need a smaller product, move right pointer down

    return False

The logic is structurally identical to the pair-sum walkthrough from "The Converging Pointers Pattern" — only the comparison operator (* instead of +) changed. That's the payoff of internalizing the pattern rather than memorizing a specific problem: once you recognize the shape, the code is a small edit away.

Now contrast that with a problem that fails the sortedness check: given an unsorted array, find whether two elements sum to a target, but you also need to know which two original indices produced that sum. Sorting the array would destroy the index information you need to return, so converging pointers cannot be applied directly without extra bookkeeping. This is exactly the situation where the O(n) time / O(n) space hash-map approach, established in "The Converging Pointers Pattern," becomes the right tool instead of forcing a two-pointer shape onto data that doesn't support it:

def two_sum_indices(nums, target):
    """
    Return the indices of two numbers that sum to target.
    Works on unsorted input because it never relies on order —
    trades O(n) extra space for that flexibility.
    """
    seen = {}  # maps value -> index where it was found
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

⚠️ Common Mistake: reaching for converging pointers out of habit whenever a problem says "pair" or "sum," without first checking whether the input is sorted or whether sorting is even compatible with what the problem asks you to return. Sorting an array to enable converging pointers is only free when the problem doesn't care about original positions — the moment index identity matters, sorting silently breaks the solution unless you carry the original indices alongside the values.

Where the Complexity Figures Fit

The complexity comparisons themselves were established in detail in "The Converging Pointers Pattern" — the O(n) time / O(1) space of a single two-pointer pass, against the O(n²) brute-force nested loop, against the O(n) time / O(n) space hash-map alternative. The decision framework above is what tells you when that O(n)/O(1) figure is actually available to you: it's available precisely when the sortedness precondition holds (or sorting is cheap and index-safe), and it degrades to the hash-map trade-off the moment that precondition is violated. Keeping the complexity figures and the applicability checklist mentally linked — rather than treating "two pointers is O(n)" as a fact detached from its precondition — is what prevents the common mistake, covered in "Common Pitfalls When Implementing Two-Pointer Solutions," of applying converging pointers to unsorted data and getting a wrong answer instead of a slow one.

Where These Patterns Reappear

The two patterns you've consolidated here aren't abstract exercises — they're the backbone of several classic problems that get their own dedicated treatment elsewhere in this roadmap. Palindrome validation is a converging-pointers problem in disguise: one pointer starts at the front of a string, one at the back, and they move inward comparing characters until they meet or a mismatch is found. Container with most water is another converging-pointers application, where the comparison target isn't a sum but a computed area, and the pointer-movement rule is justified by a slightly different monotonicity argument than the pair-sum case. Duplicate removal, meanwhile, is the canonical fast-slow application — a slow write-pointer and a fast read-pointer compact an array in a single forward pass, extending the in-place-writing mechanics previewed in "The Fast-Slow (Same-Direction) Pointers Pattern."

💡 Mental Model: think of the two patterns as two different reasons to use a second pointer at all — one pointer pair exists to shrink a search space by comparison (converging), and the other exists to maintain a controlled relationship between a read position and a write or detection position (fast-slow). Once a new problem tells you why it needs a second pointer, the pattern almost picks itself.

Practical Next Steps

As you move into problems beyond this lesson, three habits will carry the most value from what you've built here. First, before writing any code, explicitly answer the checklist questions above out loud or in a comment — stating "this is sorted, and I need a pair sum, so converging pointers" costs a few seconds and prevents the far more expensive mistake of debugging a pointer loop that was never the right shape for the problem. Second, when a problem statement combines a sort step with a pair or triplet condition (as in 3Sum), consciously decompose it into "the part that needs sorting plus converging pointers" versus "the part that's just an outer loop," rather than trying to hold the whole solution as one undifferentiated blob. Third, keep the off-by-one and duplicate-skipping pitfalls from "Common Pitfalls When Implementing Two-Pointer Solutions" close at hand during implementation — the decision framework tells you which pattern to reach for, but the pitfalls list is what keeps the resulting code correct once you're writing it.