BeginnerArrays & Strings

Two Pointers

Use two pointers moving towards each other or in the same direction to solve array problems efficiently

Time: O(n)
Space: O(1)
Pattern Overview

Core Idea

The two pointers pattern uses two indices to traverse an array or string, either from opposite ends moving towards each other, or both starting from the same position moving at different speeds. This technique reduces time complexity from O(n²) to O(n) for many problems.

When to Use

Use this pattern when dealing with sorted arrays, finding pairs with specific properties, partitioning arrays, or when you need to compare elements from different positions. It's particularly effective for problems involving palindromes, removing duplicates, or finding subarrays with certain properties.

General Recognition Cues
General indicators that this pattern might be applicable
  • Problem mentions "sorted array" or "sorted list"
  • Looking for pairs, triplets, or subarrays with specific sum/product
  • Need to find palindromes or check if string is palindrome
  • Removing duplicates or elements in-place
  • Partitioning array around a pivot
  • Comparing elements from start and end simultaneously
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Opposite Direction (Converging)

Two pointers start at opposite ends and move toward each other

When to Use This Variant
  • Sorted array with target sum/product
  • Palindrome checking or validation
  • Container/water trapping problems
  • Finding pairs with specific relationship
  • Symmetric comparison needed
Use Case
Finding pairs with target sum, palindrome checking, container problems
Advantages
  • Eliminates need for nested loops
  • Works efficiently on sorted arrays
  • Natural for symmetric problems
  • Easy to understand and implement
Implementation
def opposite_direction(arr, target):
      left, right = 0, len(arr) - 1
      
      while left < right:
          current = arr[left] + arr[right]
          
          if current == target:
              return [left, right]
          elif current < target:
              left += 1
          else:
              right -= 1
      
      return None
2

Same Direction (Fast-Slow)

Both pointers start at the beginning and move at different speeds

When to Use This Variant
  • Remove/filter elements in-place
  • Partition array around condition
  • Move elements to end/beginning
  • Maintain relative order while filtering
  • O(1) space constraint mentioned
Use Case
Removing duplicates, partitioning, in-place modifications
Advantages
  • Achieves O(1) space complexity
  • Modifies array in-place
  • Useful for filtering and partitioning
  • Maintains relative order of elements
Implementation
def same_direction(arr):
      slow = 0
      
      for fast in range(len(arr)):
          if arr[fast] != 0:  # Keep non-zero elements
              arr[slow], arr[fast] = arr[fast], arr[slow]
              slow += 1
      
      return slow  # New length
3

Multiple Pointers (3+ Pointers)

Use three or more pointers for complex partitioning or multi-way comparisons

When to Use This Variant
  • 3Sum, 4Sum, or k-Sum problems
  • Dutch National Flag problem
  • Merging k sorted arrays
  • Complex partitioning with multiple conditions
  • Multi-way comparison needed
Use Case
3Sum problems, Dutch National Flag, merging multiple arrays
Advantages
  • Handles complex multi-condition problems
  • Efficient for k-way operations
  • Reduces nested loop complexity
  • Flexible for various problem types
Implementation
def three_pointers(arr, target):
      arr.sort()
      result = []
      
      for i in range(len(arr) - 2):
          if i > 0 and arr[i] == arr[i-1]:
              continue
          
          left, right = i + 1, len(arr) - 1
          
          while left < right:
              total = arr[i] + arr[left] + arr[right]
              
              if total == target:
                  result.append([arr[i], arr[left], arr[right]])
                  left += 1
                  right -= 1
                  
                  while left < right and arr[left] == arr[left-1]:
                      left += 1
              elif total < target:
                  left += 1
              else:
                  right -= 1
      
      return result
Common Pitfalls
Watch out for these common mistakes
  • Forgetting to handle edge cases when pointers cross or meet
  • Not considering duplicate elements in sorted arrays
  • Incorrect pointer movement logic leading to infinite loops
  • Off-by-one errors when checking boundaries
  • Not handling empty arrays or single-element arrays
Code Templates
Compare implementations across different languages
def two_pointers(arr):
      left, right = 0, len(arr) - 1
      
      while left < right:
          # Process current pair
          current_sum = arr[left] + arr[right]
          
          if current_sum == target:
              return [left, right]
          elif current_sum < target:
              left += 1  # Need larger sum
          else:
              right -= 1  # Need smaller sum
      
      return []  # Not found
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(n)

Each pointer traverses the array at most once, resulting in linear time complexity.

Space Complexity
O(1)

Only uses pointer variables regardless of input size, achieving constant space.

Ready to test your knowledge?

Test your pattern recognition with interactive questions