Engineering Notes

Two Pointers

3 min read

Two Pointers

Two pointers is a technique where you use two indices to scan an array or linked list, typically moving them toward each other or at different speeds. It often turns O(n^2) solutions into O(n).

Why It Matters

Two pointers is one of the most common patterns for array and string problems. It’s simple, efficient, and shows up constantly in practice and interviews.

Patterns

1. Opposite Ends (converging)

Start one pointer at the beginning and one at the end. Move them toward each other.

# Is a string a palindrome?
def is_palindrome(s: str) -> bool:
    lo, hi = 0, len(s) - 1
    while lo < hi:
        if s[lo] != s[hi]:
            return False
        lo += 1
        hi -= 1
    return True
 
assert is_palindrome("racecar") == True
assert is_palindrome("hello") == False
 
# Two sum on sorted array — O(n) instead of O(n^2)
def two_sum_sorted(nums: list[int], target: int) -> tuple:
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return (lo, hi)
        elif s < target:
            lo += 1
        else:
            hi -= 1
    return ()
 
assert two_sum_sorted([1, 3, 5, 7, 9], 8) == (0, 4)  # 1 + 7... wait
assert two_sum_sorted([1, 3, 5, 7, 9], 12) == (1, 4)  # 3 + 9

2. Fast and Slow

Both pointers start at the beginning. One moves faster than the other.

# Detect cycle in linked list (Floyd's algorithm)
def has_cycle(head) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
 
# Remove duplicates from sorted array in-place
def remove_duplicates(nums: list[int]) -> int:
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1  # length of unique prefix
 
nums = [1, 1, 2, 2, 3, 4, 4]
length = remove_duplicates(nums)
assert nums[:length] == [1, 2, 3, 4]

3. Sliding Window (two pointers variant)

See Sliding Window for the full pattern. The left and right pointers define a window.

When to Use

  • Problem involves sorted array or linked list
  • Need to find pairs with a certain sum
  • Remove duplicates in-place
  • Detect cycles
  • Partition or rearrange arrays
  • Compare two sequences

Complexity

Usually O(n) time and O(1) space — each pointer traverses the array at most once.

Graph View

Backlinks