Two Pointers

Two pointers is a technique where two pointers iterate through the data structure in tandem until one or both pointers hit a certain condition. It's often used to search pairs in sorted arrays or to optimize space complexity.

When to Use

Problems involving sorted arrays or linked lists
Finding pairs with specific sum or property
In-place array manipulation
Palindrome or symmetry checks

Common Patterns

Opposite Direction

Pointers start at both ends and move towards each other

Example: Two sum in sorted array, container with most water

Same Direction (Fast & Slow)

Both pointers move in same direction at different speeds

Example: Remove duplicates, cycle detection

Code Templates

Python

# Opposite direction template
def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    
    while left < right:
        current_sum = arr[left] + arr[right]
        
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return [-1, -1]

# Fast & slow template
def remove_duplicates(arr):
    if not arr:
        return 0
    
    slow = 0
    for fast in range(1, len(arr)):
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]
    
    return slow + 1

C++

// Opposite direction template
vector<int> twoSumSorted(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    
    while (left < right) {
        int sum = arr[left] + arr[right];
        
        if (sum == target) {
            return {left, right};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    
    return {-1, -1};
}

// Fast & slow template
int removeDuplicates(vector<int>& arr) {
    if (arr.empty()) return 0;
    
    int slow = 0;
    for (int fast = 1; fast < arr.size(); fast++) {
        if (arr[fast] != arr[slow]) {
            slow++;
            arr[slow] = arr[fast];
        }
    }
    
    return slow + 1;
}