Two-Pointer Technique: Complete Reference

TL;DR

• Bottom line: The two-pointer technique uses two index variables traversing a data structure in a coordinated way to reduce O(n²) brute-force solutions to O(n) time with O(1) extra space.
• Key pattern: left, right = 0, len(arr)-1; while left < right: move based on condition
• Watch out for: Applying two pointers to unsorted data when the algorithm assumes sorted order.
• Works with: Arrays, strings, linked lists. Language-agnostic; no dependencies.

Constraints

• Opposite-direction (converging) pointers require sorted input or a problem where order does not affect correctness (e.g., container with most water)
• Fast/slow pointer cycle detection only works on linked lists or sequences with a single entry point into a cycle
• Never modify the collection under iteration from both pointer positions simultaneously without a dedicated write pointer
• Two pointers cannot replace a hash map for pair-sum on unsorted arrays without first sorting (adding O(n log n))
• Always validate that both pointers remain within bounds on every step; off-by-one errors are the top source of bugs

Quick Reference

Decision Tree

START
|-- Is the input a linked list?
|   |-- YES: Need cycle detection?
|   |   |-- YES --> Fast/slow pointers (Floyd's algorithm)
|   |   |-- NO: Need the middle node?
|   |       |-- YES --> Fast/slow (stop when fast reaches end)
|   |       |-- NO --> Same-direction pointers
|   |-- NO (array or string) |
|-- Is the input sorted (or can you sort it)?
|   |-- YES: Looking for a pair that satisfies a condition?
|   |   |-- YES --> Opposite-ends (converging) pointers
|   |   |-- NO: Need to remove/deduplicate in-place?
|   |       |-- YES --> Same-direction read/write pointers
|   |       |-- NO --> Consider binary search instead
|   |-- NO (unsorted):
|       |-- Can you afford O(n log n) sorting first?
|       |   |-- YES --> Sort, then use converging pointers
|       |   |-- NO --> Use a hash map/set instead (O(n) time, O(n) space)
|-- Need to partition into regions (e.g., <pivot, ==pivot, >pivot)?
|   |-- YES --> Three-pointer / Dutch National Flag
|-- Need longest/shortest substring with a constraint?
|   |-- YES --> Sliding window (see related unit)
|-- DEFAULT --> Brute force or hash map

Step-by-Step Guide

1. Identify the pointer pattern

Determine which variant fits your problem. If you need to find a pair in a sorted array, use converging pointers. If you need to detect a cycle, use fast/slow. If you need to remove elements in-place, use read/write pointers. [src1]

Verify: Can you express the loop invariant? e.g., "Everything to the left of slow is processed and valid."

2. Initialize pointers correctly

For converging: left = 0, right = len(arr) - 1. For same-direction: slow = 0, fast = 0 (or fast = 1). For linked lists: slow = head, fast = head. [src2]

Verify: Both pointers point to valid positions in the data structure before the loop starts.

3. Define the loop condition

Converging: while left < right. Same-direction: while fast < len(arr). Linked list: while fast is not None and fast.next is not None. [src5]

Verify: The loop terminates in all cases. Converging pointers always reduce the gap by at least 1 per iteration.

4. Implement the movement logic

Inside the loop, decide which pointer to advance based on the problem condition. For converging pointers on two-sum: if arr[left] + arr[right] < target, increment left; if greater, decrement right; if equal, return the pair. [src1]

Verify: Each iteration advances at least one pointer, guaranteeing O(n) termination.

5. Handle edge cases

Empty input, single element, all duplicates, already-at-target. For linked lists: null head, single node, cycle that includes the head. [src3]

Verify: Test with arrays of length 0, 1, 2 and linked lists with 0, 1, 2 nodes.

Code Examples

Python: Two Sum on Sorted Array (Converging Pointers)

# Input:  sorted array of integers, integer target
# Output: tuple of 1-indexed positions (i, j) where arr[i]+arr[j]==target

def two_sum_sorted(numbers: list[int], target: int) -> tuple[int, int]:
    left, right = 0, len(numbers) - 1
    while left < right:
        current = numbers[left] + numbers[right]
        if current == target:
            return (left + 1, right + 1)  # 1-indexed
        elif current < target:
            left += 1    # need a larger sum
        else:
            right -= 1   # need a smaller sum
    raise ValueError("No solution found")

Python: Container With Most Water (Converging Pointers)

# Input:  list of non-negative integers representing heights
# Output: maximum water area between any two lines

def max_area(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        width = right - left
        h = min(height[left], height[right])
        best = max(best, width * h)
        if height[left] < height[right]:
            left += 1    # move the shorter line inward
        else:
            right -= 1
    return best

JavaScript: Remove Duplicates In-Place (Read/Write Pointers)

// Input:  sorted array of integers (nums)
// Output: length of array with duplicates removed; nums mutated in-place

function removeDuplicates(nums) {
  if (nums.length === 0) return 0;
  let slow = 0;                      // write pointer
  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[fast] !== nums[slow]) { // found a new unique element
      slow++;
      nums[slow] = nums[fast];       // write it at the next position
    }
  }
  return slow + 1;                   // length of unique portion
}

Python: Linked List Cycle Detection (Floyd's Algorithm)

# Input:  head of a singly linked list (may contain a cycle)
# Output: True if cycle exists, False otherwise

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

def has_cycle(head: ListNode | None) -> bool:
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next          # 1 step
        fast = fast.next.next     # 2 steps
        if slow is fast:          # pointers met inside the cycle
            return True
    return False                  # fast reached end; no cycle

Java: Valid Palindrome (Converging Pointers with Filtering)

// Input:  string s with mixed characters
// Output: true if s is a palindrome considering only alphanumeric chars

public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        while (left < right && !Character.isLetterOrDigit(s.charAt(left)))
            left++;                       // skip non-alphanumeric
        while (left < right && !Character.isLetterOrDigit(s.charAt(right)))
            right--;                      // skip non-alphanumeric
        if (Character.toLowerCase(s.charAt(left)) !=
            Character.toLowerCase(s.charAt(right)))
            return false;
        left++;
        right--;
    }
    return true;
}

Anti-Patterns

Wrong: Using two pointers on unsorted data for pair-sum

# BAD -- two-pointer converging requires sorted input
def two_sum_wrong(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1
        else:
            right -= 1
    return []  # may miss valid pairs because array is unsorted

Correct: Sort first or use a hash map

# GOOD -- sort first, then use converging pointers
def two_sum_correct(nums, target):
    indexed = sorted(enumerate(nums), key=lambda x: x[1])
    left, right = 0, len(indexed) - 1
    while left < right:
        s = indexed[left][1] + indexed[right][1]
        if s == target:
            return [indexed[left][0], indexed[right][0]]
        elif s < target:
            left += 1
        else:
            right -= 1
    return []

# OR: use a hash map for O(n) without sorting
def two_sum_hashmap(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:
            return [seen[complement], i]
        seen[n] = i
    return []

Wrong: Not skipping duplicates in 3Sum

# BAD -- produces duplicate triplets
def three_sum_wrong(nums, target=0):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == target:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
            elif s < target:
                left += 1
            else:
                right -= 1
    return result  # contains duplicate triplets

Correct: Skip duplicate values after finding a match

# GOOD -- skip duplicates at all three positions
def three_sum_correct(nums, target=0):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:  # skip duplicate i
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == target:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1   # skip duplicate left
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1  # skip duplicate right
                left += 1
                right -= 1
            elif s < target:
                left += 1
            else:
                right -= 1
    return result

Wrong: Returning meeting point as cycle start

# BAD -- returns the meeting point, NOT the cycle start
def find_cycle_start_wrong(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return slow  # this is the meeting point, NOT the cycle start
    return None

Correct: Reset one pointer to head after detection

# GOOD -- Floyd's algorithm phase 2: find the cycle entry
def find_cycle_start_correct(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # Phase 2: move one pointer to head, advance both by 1
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow  # this is the actual cycle entry node
    return None

Common Pitfalls

• Off-by-one in loop condition: Using left <= right instead of left < right for pair-finding causes accessing the same element twice. Fix: use left < right for distinct pairs. [src1]
• Forgetting to sort: Converging pointers on unsorted data silently produces wrong results with no error. Fix: always sort() first or verify the input is pre-sorted. [src3]
• Infinite loop from not advancing pointers: If neither pointer moves when a condition is not met, the loop never terminates. Fix: ensure at least one pointer advances on every iteration. [src5]
• Mutating during traversal: Writing to arr[fast] while also reading from arr[slow] when slow == fast causes data corruption. Fix: use distinct read and write pointers that never overlap incorrectly. [src4]
• Not handling duplicates: In problems like 3Sum, failing to skip duplicate values produces redundant results and wastes time. Fix: after finding a match, advance pointers past all equal elements. [src6]
• Assuming fast/slow works on doubly linked lists: The tortoise-and-hare algorithm does not detect cycles in doubly linked lists. Fix: use a hash set for doubly linked lists. [src2]

When to Use / When Not to Use

Important Caveats

• The two-pointer technique is a conceptual pattern, not a specific algorithm. Its correctness depends entirely on the problem's structure (monotonicity, sorted order, or cycle properties).
• When sorting is required as a preprocessing step, the overall complexity becomes O(n log n), not O(n). The two-pointer traversal itself is O(n), but the sort dominates.
• For problems on strings with Unicode characters, pointer arithmetic on byte indices can be wrong. Always iterate by character (e.g., Python handles this natively; in Java/JavaScript, use code point iteration for astral plane characters).
• The fast/slow pointer technique for finding the cycle entry point relies on a mathematical proof (distance relationship). Simply detecting the meeting point is not sufficient to find the cycle start; you must reset one pointer to the head.
• Two-pointer solutions often have subtle edge cases with empty inputs, single-element inputs, and all-equal elements. Always test these boundary conditions.