Two Pointers Pattern

The two pointers pattern uses two indices that move toward each other (or at different speeds) to solve in O(n) what would otherwise be O(n²). It shows up constantly on sorted arrays, palindrome checks, and linked-list problems.

When to recognize this pattern

• The array is sorted (or you can sort it) and you're searching for a pair/triple with a target relationship.
• You're comparing elements from both ends inward (palindrome, container, trapping water).
• A linked-list problem needs fast/slow pointers (cycle detection, middle node, nth-from-end).

The template

The converging template walks two pointers inward, moving the one that improves the objective:

def two_pointers(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        total = arr[left] + arr[right]
        if total == target:
            return [left, right]
        elif total < target:
            left += 1          # need a bigger sum
        else:
            right -= 1         # need a smaller sum
    return []

Worked examples

3Sum

Problem: Find all unique triplets in the array that sum to zero.

Sort, fix one element, and run converging two pointers on the rest. Skip duplicates to keep triplets unique.

def threeSum(nums):
    nums.sort()
    res = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s < 0: left += 1
            elif s > 0: right -= 1
            else:
                res.append([nums[i], nums[left], nums[right]])
                left += 1; right -= 1
                while left < right and nums[left] == nums[left-1]: left += 1
                while left < right and nums[right] == nums[right+1]: right -= 1
    return res

O(n²) time after the O(n log n) sort. The duplicate-skipping is what most candidates get wrong — skip equal values at every level.

Container with most water

Problem: Given heights, find two lines that hold the most water.

Start at both ends; the area is limited by the shorter line, so move the shorter pointer inward.

def maxArea(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        best = max(best, min(height[left], height[right]) * (right - left))
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

O(n) time, O(1) space. Moving the taller pointer can never increase the area, so always move the shorter one.

Linked list cycle (fast/slow)

Problem: Determine if a linked list has a cycle.

Floyd's algorithm: a slow pointer moves one step, a fast pointer two; if they meet, there's a cycle.

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

O(n) time, O(1) space. The fast/slow variant is the other half of the two-pointer family — same idea, different speeds instead of converging ends.

Variations & pitfalls

• Converging vs fast/slow. Converging works on sorted arrays from both ends; fast/slow works on linked lists and cycle problems.
• Remove duplicates in place (read/write pointers) is a two-pointer variant for arrays.
• Pitfall: forgetting to skip duplicate values in problems like 3Sum, producing repeated answers.

FAQ

When should I use two pointers?

When the array is sorted (or sortable) and you're finding a pair or triple with a target relationship, when you compare elements from both ends inward (palindromes, container, trapping water), or for linked-list problems that need fast/slow pointers like cycle detection.

What are the two main two-pointer templates?

Converging pointers start at both ends of a sorted array and move inward based on the objective. Fast/slow pointers move at different speeds through a linked list - used for cycle detection, finding the middle, or the nth node from the end.

Why move the shorter line in 'container with most water'?

The water area is limited by the shorter of the two lines, so moving the taller pointer inward can only keep or reduce the height while reducing the width - it can never improve the area. Moving the shorter pointer is the only move that can help.

What's the most common two-pointer bug?

Failing to skip duplicate values in problems like 3Sum, which produces duplicate triplets. After recording a result, advance both pointers past any equal neighbors.

What is Floyd's cycle detection?

A fast/slow two-pointer technique: the slow pointer advances one node per step, the fast pointer two. If the list has a cycle they eventually meet; if the fast pointer reaches the end, there's no cycle. It uses O(1) space.