Two Pointers Technique

The two pointers technique is a pattern where you use two indices to traverse a data structure, often from different ends or at different speeds.

When to Use Two Pointers

Searching for pairs in a sorted array
Reversing or comparing elements
Finding subarrays with certain properties
Removing duplicates

Pattern 1: Opposite Direction

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

Example: Is Palindrome?

def is_palindrome(s):
    left = 0
    right = len(s) - 1

    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1

    return True

print(is_palindrome("racecar"))  # True
print(is_palindrome("hello"))    # False

Example: Two Sum (Sorted Array)

Given a sorted array, find two numbers that add up to a target:

def two_sum_sorted(numbers, target):
    left = 0
    right = len(numbers) - 1

    while left < right:
        current_sum = numbers[left] + numbers[right]

        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1   # Need larger sum
        else:
            right -= 1  # Need smaller sum

    return []  # No solution found

nums = [1, 2, 3, 4, 6]
print(two_sum_sorted(nums, 6))  # [1, 3] (indices of 2 and 4)

Pattern 2: Same Direction (Fast/Slow)

Both pointers move in the same direction, but at different speeds.

Example: Remove Duplicates (In-Place)

def remove_duplicates(nums):
    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 elements

nums = [1, 1, 2, 2, 3, 4, 4]
length = remove_duplicates(nums)
print(nums[:length])  # [1, 2, 3, 4]

Example: Move Zeros to End

def move_zeros(nums):
    slow = 0

    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

    return nums

print(move_zeros([0, 1, 0, 3, 12]))  # [1, 3, 12, 0, 0]

Pattern 3: Sliding Window Variant

Sometimes two pointers define a "window" in the array:

def longest_substring_without_repeating(s):
    seen = set()
    left = 0
    max_length = 0

    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1

        seen.add(s[right])
        max_length = max(max_length, right - left + 1)

    return max_length

print(longest_substring_without_repeating("abcabcbb"))  # 3 ("abc")

Key Insights

Sorted arrays - Two pointers from opposite ends often work well
In-place modifications - Fast/slow pointer pattern
Time complexity - Usually O(n) since each pointer moves at most n times
Space complexity - Usually O(1) since we only use pointer variables

Practice Problems

After this lesson, try these problems:
- Two Sum (if the array is sorted)
- Valid Palindrome
- Container With Most Water
- 3Sum

Tip: When you see "find a pair" or "in-place" in a problem, consider two pointers!