Skip to main content

Two Pointers Technique

TL;DR​

Two pointers uses two indices/references to traverse an array or string efficiently. For sorted arrays, start pointers at opposite ends: move inward based on comparison. For fast-slow pointers, traverse at different speeds to detect patterns. This technique reduces O(n²) brute force to O(n) or O(n log n). Works for finding pairs, removing duplicates, partitioning, and validating palindromes.

Core Concepts​

Opposite Direction Pointers​

Approach: Place one pointer at start, one at end. Move toward center based on problem-specific logic.

When to use:

  • Sorted arrays where you need pairs
  • Finding elements satisfying constraint
  • Partitioning or rearrangement problems

Key insight: Since array is sorted, moving pointers intelligently eliminates entire search space. If current sum is too large, moving right pointer left decreases sum. If too small, moving left pointer right increases sum.

Time complexity: O(n) single pass, vs O(n²) checking all pairs

Same Direction Pointers​

Approach: Both pointers start at beginning, move at same or different speeds.

Variations:

  • Fast-slow pointers: One moves 1 step, other moves k steps. Detects cycles, finds middle, meets at kth element
  • Sliding window: Maintain distance between pointers representing current window

Time complexity: O(n) single pass, no backtracking

Two Sum Problems​

Two Sum: Given sorted array, find two numbers summing to target.

  • Place left pointer at start, right at end
  • If sum equals target, found pair
  • If sum too small, move left pointer right (increase sum)
  • If sum too large, move right pointer left (decrease sum)

K Sum: Generalize two-sum with k numbers. Fix k-2 numbers with nested loops, apply two-sum on remainder.

Palindrome Validation​

Valid Palindrome: Check if string reads same forwards and backwards.

  • Place pointers at opposite ends
  • Compare characters, moving inward
  • Ignore non-alphanumeric characters
  • Case-insensitive comparison

Early termination: Can return false immediately on mismatch

Merge and Partitioning​

Merge sorted arrays: Two pointers in source arrays, one in target. Compare elements, copy smaller.

Remove duplicates: Slow pointer marks write position, fast pointer finds next unique element.

Partition around pivot: Move left to first "too large" element, right to first "too small" element. Swap and continue.

Key Algorithms and Techniques​

Two Sum with Two Pointers​

Sort array O(n log n), then two pointers O(n). Total O(n log n).

Three Sum Problem​

Fix each element O(n), apply two-sum on remainder O(n). Total O(n²).

Container with Most Water​

Two pointers from ends, move pointer at smaller height. Greedy pruning ensures optimality.

Remove Duplicates In-Place​

Slow pointer for write position, fast for read. Single pass O(n), O(1) space.

Valid Palindrome​

Two pointers from ends, skip non-alphanumeric. O(n) time, O(1) space.

Practical Example​

# Two sum with sorted array
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 [arr[left], arr[right]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return None

# Three sum - find all triplets summing to target
def three_sum(arr, target):
    arr.sort()
    result = []
    for i in range(len(arr) - 2):
        # Two sum on remainder
        left, right = i + 1, len(arr) - 1
        while left < right:
            current_sum = arr[i] + arr[left] + arr[right]
            if current_sum == target:
                result.append([arr[i], arr[left], arr[right]])
                left += 1
                right -= 1
            elif current_sum < target:
                left += 1
            else:
                right -= 1
    return result

# Valid palindrome
def is_valid_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        # Skip non-alphanumeric
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        # Compare case-insensitive
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

# Remove duplicates in-place
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

# Container with most water
def max_area(heights):
    left, right = 0, len(heights) - 1
    max_area_val = 0
    while left < right:
        width = right - left
        height = min(heights[left], heights[right])
        area = width * height
        max_area_val = max(max_area_val, area)
        # Move pointer with smaller height
        if heights[left] < heights[right]:
            left += 1
        else:
            right -= 1
    return max_area_val

# Test cases
print(two_sum_sorted([1, 2, 3, 4, 5], 7))  # [2, 5]
print(three_sum([1, 0, -1, 0, -2, 2], 0))  # All triplets summing to 0
print(is_valid_palindrome("A man, a plan, a canal: Panama"))  # True
print(remove_duplicates([1, 1, 2, 2, 3]))  # Returns 3, array becomes [1, 2, 3]
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49

Common Pitfalls​

warning

Not handling duplicates: When removing duplicates or finding sums, duplicates can skip valid pairs. Advance both pointers when condition met to avoid revisiting.

Incorrect movement logic: Moving wrong pointer makes algorithm miss solutions. For two-sum: if sum too small, need to increase it (move left pointer right), not decrease it.

Off-by-one in palindrome: Comparing arr[left] vs arr[right] when left == right on odd-length array compares element to itself. Use left < right condition.

Assuming sorted input: Two pointers usually requires sorted input. If input unsorted, sort first (O(n log n)) then apply two pointers.

Forgetting to skip non-alphanumeric: In valid palindrome, must skip non-letter/digit characters. Loop to advance pointers while characters invalid.

Self-Check​

  1. Why does moving the pointer pointing to the smaller height guarantee we won't miss optimal container in the water problem?
  2. Explain how two pointers reduce two-sum from O(n²) brute force to O(n). What preprocessing is required?
  3. How does the fast-slow pointer technique detect cycles in linked lists?

One Takeaway​

info

Two pointers is a powerful technique that transforms O(n²) problems into O(n) solutions. Mastering when to move which pointer, handling edge cases, and adapting the pattern to different problems makes you solve array/string problems efficiently. The key insight: sorted structure or specific movement rules allow pruning vast solution spaces.

References​

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • McDowell, G. L. (2015). Cracking the Coding Interview (6th ed.). CareerCup.