Two Pointers Pattern

The Two Pointers pattern utilizes two index variables (pointers) to traverse a linear data structure simultaneously, typically moving towards each other or at different speeds, to solve search or modification tasks in a single pass.

Recognition Signals

You should consider this pattern if you see any of the following cues in the problem description:

• The input array or list is sorted (or can be sorted without affecting the correctness of the indices).
• The problem asks you to find pairs of elements that sum to a target value.
• You need to swap or reverse elements in-place without using extra memory allocation.
• The structure is a linked list and you need to detect cycles or find middle nodes (Fast & Slow pointers).

How It Works

Instead of checking all pairs using nested loops (O(n²)), you initialize two pointers at different locations (e.g. one at the start left and one at the end right). You then compare elements, and based on the comparison, you increment left or decrement right to reduce the search space.

For example, to find if a sorted list contains a pair that sums to 9:

1. Initialize: nums = [1, 2, 4, 6, 8], target = 9, left = 0, right = 4.
2. Step 1: nums[0] + nums[4] = 1 + 8 = 9. Match found. Return index pair [0, 4].
3. If sum was smaller than 9, you would increment left. If larger, you would decrement right.

Complexity, With Caveats

• Time Complexity: O(n) where n is the number of elements. The pointers move towards each other or at constant offsets, visiting each element at most once.
• Space Complexity: O(1) auxiliary space, as you only need two integer variables to track indices.

Minimal Code Template

public class TwoPointersTemplate {
    // Opposite Direction (Two Sum on Sorted Array)
    public boolean hasTargetSum(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int currentSum = nums[left] + nums[right];
            if (currentSum == target) {
                return true;
            } else if (currentSum < target) {
                left++; // increase sum
            } else {
                right--; // decrease sum
            }
        }
        return false;
    }
}

# Opposite Direction (Two Sum on Sorted Array)
def has_target_sum(nums: list[int], target: int) -> bool:
    left = 0
    right = len(nums) - 1

    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return True
        elif current_sum < target:
            left += 1  # increase sum
        else:
            right -= 1  # decrease sum
    return False

#include <vector>

class TwoPointersTemplate {
public:
    // Opposite Direction (Two Sum on Sorted Array)
    bool hasTargetSum(const std::vector<int>& nums, int target) {
        int left = 0;
        int right = (int)nums.size() - 1;

        while (left < right) {
            int currentSum = nums[left] + nums[right];
            if (currentSum == target) {
                return true;
            } else if (currentSum < target) {
                left++; // increase sum
            } else {
                right--; // decrease sum
            }
        }
        return false;
    }
};

Where This Pattern Falls Short

• Unsorted inputs: Two pointers logic relies on elements being ordered. If the array is unsorted, you must sort it first, which increases time complexity to O(n log n). If sorting is not allowed or loses required index mapping (like in Two Sum where original indices are needed), you should use Arrays & Hashing instead.
• Multi-element combinations: Reaching beyond two elements (like finding triplets or quadruplets) requires nesting loops, which increases complexity to O(n²).

Related Patterns, Compared

• Arrays & Hashing: choose this instead when the input is unsorted and you cannot sort it, as it allows constant-time lookups using O(n) extra space.
• Sliding Window: choose this instead when you need to maintain a contiguous subarray of dynamic size rather than comparing two discrete points.

Frequently Asked Questions

Why does Two Pointers only work on sorted arrays? Because sorting establishes a monotonic relationship. If you know that increasing the left pointer always increases the sum (and decreasing the right pointer always decreases the sum), you can make greedy decision rules to eliminate search options.

What is the difference between Two Pointers and Fast & Slow pointers? Two Pointers typically moves coordinates from opposite ends inwards. Fast & Slow pointers (Tortoise and Hare) move in the same direction at different speeds (slow moves 1 step, fast moves 2 steps) to detect cycles or find middle points in linked structures.

Can we use Two Pointers on linked lists? Yes. You can traverse linked list nodes using node pointers instead of integer array indices.