Two Pointer Technique: Solving Array Problems Efficiently

Introduction

The two pointer technique is a powerful pattern for solving array and string problems efficiently. By maintaining two pointers that traverse from different directions or speeds, we can often reduce time complexity from O(n^2) to O(n).

Pattern 1: Opposite Direction

Two pointers start at opposite ends and move toward each other.

# Two Sum II (sorted array)
def two_sum_sorted(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return [left + 1, right + 1]
        elif s < target:
            left += 1
        else:
            right -= 1
    return []

# Container With Most Water
def max_area(height):
    left, right = 0, len(height) - 1
    result = 0
    while left < right:
        w = right - left
        area = w * min(height[left], height[right])
        result = max(result, area)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return result

Pattern 2: Fast-Slow Pointers

Both pointers move same direction at different speeds. Used for removing duplicates, partitioning arrays, and cycle detection.

# Remove Duplicates from Sorted Array
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

# Move Zeroes
def move_zeroes(nums):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

Pattern 3: Sliding Window

A special case maintaining a window that slides through the array.

# Longest Substring Without Repeating Characters
def length_of_longest_substring(s):
    chars = set()
    left = max_len = 0
    for right in range(len(s)):
        while s[right] in chars:
            chars.remove(s[left])
            left += 1
        chars.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len

# Minimum Size Subarray Sum
def min_subarray_len(target, nums):
    left = cur = 0
    result = float('inf')
    for right in range(len(nums)):
        cur += nums[right]
        while cur >= target:
            result = min(result, right - left + 1)
            cur -= nums[left]
            left += 1
    return result if result != float('inf') else 0

Three Sum

Uses fixed pointer plus two-pointer technique.

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

Cycle Detection

Floyd's tortoise and hare algorithm detects cycles in linked lists with O(1) space.

def has_cycle(head):
    if not head or not head.next: return False
    slow, fast = head, head.next
    while slow != fast:
        if not fast or not fast.next: return False
        slow = slow.next
        fast = fast.next.next
    return True

When to Use

Consider two pointers when dealing with sorted arrays, finding pairs/triplets, removing elements in-place, detecting patterns, or optimizing from O(n^2) to O(n). Look for keywords like in-place, sorted, pairs, or sliding window.