Two Pointers Technique

Overview

The two pointers technique maintains two index variables that traverse an array or string according to specific movement rules. This approach transforms problems that would require nested loops into single-pass solutions, reducing algorithmic complexity.

The technique applies to problems involving searching, partitioning, or finding relationships between elements in ordered or unordered collections. Common applications include finding pairs with specific sums, detecting palindromes, partitioning arrays around pivot values, and removing duplicates from sorted sequences.

Two pointers work by establishing positions at different locations in the data structure and moving them based on conditions derived from the problem requirements. The pointers may start at opposite ends and converge, start together and move at different speeds, or maintain a window of variable size.

# Finding a pair that sums to target in sorted array
def two_sum(arr, target)
  left = 0
  right = arr.length - 1
  
  while left < right
    sum = arr[left] + arr[right]
    return [left, right] if sum == target
    
    sum < target ? left += 1 : right -= 1
  end
  
  nil
end

two_sum([1, 2, 3, 4, 6], 6)
# => [1, 3]  # arr[1] + arr[3] = 2 + 4 = 6

The technique originated from analysis of sorting and searching algorithms where maintaining multiple positions within a data structure proved more efficient than repeated iterations. The approach became formalized as a distinct pattern through competitive programming and algorithm optimization studies.

Key Principles

The two pointers technique operates on the principle that certain relationships between elements can be determined by comparing values at different positions and adjusting those positions based on the comparison results. This eliminates the need for examining every possible pair or combination.

Pointer Movement Rules

Pointer advancement follows deterministic rules derived from problem constraints. In sorted array problems, comparing the sum of pointed values against a target determines which pointer moves: if the sum exceeds the target, the right pointer decrements to reduce the sum; if below target, the left pointer increments to increase it. This guarantees that all valid pairs are examined without checking every combination.

Convergence Conditions

The algorithm terminates when pointers meet, cross, or satisfy problem-specific conditions. For opposite-end pointers, termination occurs when left >= right. For same-direction pointers, termination happens when the faster pointer reaches the boundary. The invariant—the condition that remains true throughout execution—defines correctness.

Search Space Reduction

Each pointer movement eliminates a portion of the search space. When searching for a pair sum in a sorted array, moving the left pointer right eliminates all pairs involving the previous left element, as those have been examined. Moving right pointer left similarly eliminates pairs with the previous right element. This property ensures O(n) time complexity.

# Demonstrating search space reduction
def find_pair_sum_verbose(arr, target)
  left = 0
  right = arr.length - 1
  iterations = 0
  
  while left < right
    iterations += 1
    sum = arr[left] + arr[right]
    
    if sum == target
      puts "Found in #{iterations} iterations (vs #{arr.length * (arr.length - 1) / 2} for brute force)"
      return [arr[left], arr[right]]
    end
    
    sum < target ? left += 1 : right -= 1
  end
  
  nil
end

Variants and Classifications

Three primary variants exist based on pointer positioning and movement:

Opposite-ends pointers start at array boundaries and converge toward the center. This variant works when the data structure has ordering properties that relate boundary elements to interior elements.

Same-direction pointers move in the same direction at different speeds or with different advancement rules. The fast-slow pointer pattern detects cycles, finds middle elements, or identifies specific positions. The sliding window pattern maintains a range of elements meeting certain criteria.

Partitioning pointers segregate elements into regions based on conditions, with one pointer tracking the boundary between regions and another scanning for elements to swap across the boundary.

Ruby Implementation

Ruby arrays provide zero-indexed access with negative indexing for end-relative positions. The two pointers technique uses these features along with Ruby's iteration methods and range operations.

Array Access Patterns

Ruby supports both positive indices (0 to length-1) and negative indices (-1 for last element, -2 for second-to-last). While negative indices offer convenience, two pointers implementations typically use positive indices with explicit length calculations for clarity and consistent behavior.

def reverse_array(arr)
  left = 0
  right = arr.length - 1
  
  while left < right
    arr[left], arr[right] = arr[right], arr[left]
    left += 1
    right -= 1
  end
  
  arr
end

reverse_array([1, 2, 3, 4, 5])
# => [5, 4, 3, 2, 1]

String Manipulation

Ruby strings require conversion to character arrays for in-place modification since strings are mutable but individual character replacement differs from array element replacement. The chars method converts strings to arrays, and join reconstructs the string.

def is_palindrome(str)
  chars = str.downcase.gsub(/[^a-z0-9]/, '').chars
  left = 0
  right = chars.length - 1
  
  while left < right
    return false if chars[left] != chars[right]
    left += 1
    right -= 1
  end
  
  true
end

is_palindrome("A man, a plan, a canal: Panama")
# => true

Range and Slice Operations

Ruby ranges (start..end or start...end) represent contiguous sequences. Two pointers define dynamic ranges that change during iteration. The slice method or range indexing extracts subarrays between pointer positions.

def find_max_sum_subarray(arr, k)
  return nil if k > arr.length
  
  # Initialize window
  window_sum = arr[0...k].sum
  max_sum = window_sum
  max_start = 0
  
  # Slide window
  left = 0
  right = k
  
  while right < arr.length
    window_sum = window_sum - arr[left] + arr[right]
    if window_sum > max_sum
      max_sum = window_sum
      max_start = left + 1
    end
    left += 1
    right += 1
  end
  
  { sum: max_sum, subarray: arr[max_start, k] }
end

find_max_sum_subarray([1, 4, 2, 10, 23, 3, 1, 0, 20], 4)
# => {:sum=>39, :subarray=>[4, 2, 10, 23]}

Enumerable Integration

While two pointers typically use while loops for explicit pointer control, Ruby enumerables offer alternative approaches for specific patterns. The each_cons method provides sliding windows, and each_with_index tracks positions during iteration.

# Traditional two pointer approach
def remove_duplicates_sorted(arr)
  return 0 if arr.empty?
  
  write_pos = 1
  
  (1...arr.length).each do |read_pos|
    if arr[read_pos] != arr[read_pos - 1]
      arr[write_pos] = arr[read_pos]
      write_pos += 1
    end
  end
  
  write_pos
end

nums = [1, 1, 2, 2, 2, 3, 4, 4, 5]
length = remove_duplicates_sorted(nums)
nums[0...length]
# => [1, 2, 3, 4, 5]

In-Place Modification

Many two pointer algorithms modify arrays in-place to achieve O(1) space complexity. Ruby arrays support parallel assignment for swaps and direct index assignment for element updates.

def move_zeros_to_end(arr)
  write_pos = 0
  
  # Move all non-zeros to front
  arr.each_with_index do |val, read_pos|
    if val != 0
      arr[write_pos] = val
      write_pos += 1
    end
  end
  
  # Fill remaining positions with zeros
  (write_pos...arr.length).each { |i| arr[i] = 0 }
  
  arr
end

move_zeros_to_end([0, 1, 0, 3, 12])
# => [1, 3, 12, 0, 0]

Common Patterns

The two pointers technique manifests in distinct patterns, each suited to specific problem characteristics. Recognizing these patterns accelerates problem-solving and implementation.

Opposite Ends Convergence

This pattern places pointers at array boundaries and moves them toward each other based on comparison results. The pattern requires some ordering or symmetry property in the data.

def three_sum_closest(nums, target)
  nums.sort!
  closest_sum = Float::INFINITY
  min_diff = Float::INFINITY
  
  nums.each_with_index do |num, i|
    next if i > 0 && num == nums[i - 1]  # Skip duplicates
    
    left = i + 1
    right = nums.length - 1
    
    while left < right
      current_sum = num + nums[left] + nums[right]
      diff = (current_sum - target).abs
      
      if diff < min_diff
        min_diff = diff
        closest_sum = current_sum
      end
      
      current_sum < target ? left += 1 : right -= 1
    end
  end
  
  closest_sum
end

Fast-Slow Pointer

The fast-slow pattern uses two pointers advancing at different rates. This detects cycles, finds middle elements, or identifies positions at fractional distances through the structure.

def find_middle_node(linked_list_array)
  return nil if linked_list_array.empty?
  
  slow = 0
  fast = 0
  
  while fast < linked_list_array.length - 1 && 
        fast + 1 < linked_list_array.length
    slow += 1
    fast += 2
  end
  
  linked_list_array[slow]
end

find_middle_node([1, 2, 3, 4, 5])
# => 3

Sliding Window

The sliding window maintains a contiguous range of elements meeting specific criteria. Both pointers move in the same direction, with the window expanding or contracting based on conditions.

def longest_substring_without_repeating(str)
  char_positions = {}
  left = 0
  max_length = 0
  
  str.chars.each_with_index do |char, right|
    if char_positions.key?(char) && char_positions[char] >= left
      left = char_positions[char] + 1
    end
    
    char_positions[char] = right
    max_length = [max_length, right - left + 1].max
  end
  
  max_length
end

longest_substring_without_repeating("abcabcbb")
# => 3  # "abc"

Partition Pattern

The partition pattern separates elements into regions based on conditions. One pointer tracks the boundary between regions while another scans for elements to move.

def partition_array(arr, pivot)
  left = 0
  right = arr.length - 1
  
  while left <= right
    # Find element on left that should be on right
    left += 1 while left <= right && arr[left] < pivot
    
    # Find element on right that should be on left
    right -= 1 while left <= right && arr[right] >= pivot
    
    if left < right
      arr[left], arr[right] = arr[right], arr[left]
      left += 1
      right -= 1
    end
  end
  
  arr
end

partition_array([3, 5, 2, 7, 1, 9, 4], 5)
# => [3, 4, 2, 1, 5, 9, 7]  # Elements < 5 before elements >= 5

Multiple Pointer Coordination

Some problems require coordinating more than two pointers simultaneously, each with distinct movement rules.

def remove_element(arr, val)
  write_pos = 0
  
  arr.each do |element|
    if element != val
      arr[write_pos] = element
      write_pos += 1
    end
  end
  
  arr[0...write_pos]
end

remove_element([3, 2, 2, 3, 4, 2, 5], 2)
# => [3, 3, 4, 5]

Practical Examples

Container With Most Water

Given heights representing vertical lines, find two lines that form a container holding maximum water. The area equals the minimum height multiplied by the distance between lines.

def max_area(heights)
  left = 0
  right = heights.length - 1
  max_water = 0
  
  while left < right
    # Calculate current area
    width = right - left
    height = [heights[left], heights[right]].min
    current_area = width * height
    max_water = [max_water, current_area].max
    
    # Move pointer at shorter height
    # Moving taller pointer cannot increase area
    if heights[left] < heights[right]
      left += 1
    else
      right -= 1
    end
  end
  
  max_water
end

max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])
# => 49  # Lines at index 1 (height 8) and index 8 (height 7)

Trapping Rain Water

Calculate water trapped between elevation bars after rainfall. Water at each position equals the minimum of maximum heights to the left and right, minus the current height.

def trap_rain_water(heights)
  return 0 if heights.length < 3
  
  left = 0
  right = heights.length - 1
  left_max = 0
  right_max = 0
  water = 0
  
  while left < right
    if heights[left] < heights[right]
      if heights[left] >= left_max
        left_max = heights[left]
      else
        water += left_max - heights[left]
      end
      left += 1
    else
      if heights[right] >= right_max
        right_max = heights[right]
      else
        water += right_max - heights[right]
      end
      right -= 1
    end
  end
  
  water
end

trap_rain_water([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])
# => 6

Sort Colors (Dutch National Flag)

Sort an array containing only 0s, 1s, and 2s in-place using a single pass. Three pointers maintain boundaries between color regions.

def sort_colors(nums)
  low = 0      # Boundary for 0s
  mid = 0      # Current element
  high = nums.length - 1  # Boundary for 2s
  
  while mid <= high
    case nums[mid]
    when 0
      nums[low], nums[mid] = nums[mid], nums[low]
      low += 1
      mid += 1
    when 1
      mid += 1
    when 2
      nums[mid], nums[high] = nums[high], nums[mid]
      high -= 1
      # Don't increment mid - need to examine swapped element
    end
  end
  
  nums
end

sort_colors([2, 0, 2, 1, 1, 0])
# => [0, 0, 1, 1, 2, 2]

Minimum Window Substring

Find the smallest substring containing all characters from a pattern string, including duplicates.

def min_window_substring(s, t)
  return "" if s.empty? || t.empty?
  
  # Build character frequency map for pattern
  pattern_freq = Hash.new(0)
  t.each_char { |c| pattern_freq[c] += 1 }
  
  required = pattern_freq.length
  formed = 0
  window_counts = Hash.new(0)
  
  left = 0
  min_len = Float::INFINITY
  min_left = 0
  
  s.each_char.with_index do |char, right|
    window_counts[char] += 1
    
    if pattern_freq.key?(char) && 
       window_counts[char] == pattern_freq[char]
      formed += 1
    end
    
    # Contract window while valid
    while formed == required && left <= right
      # Update minimum window
      if right - left + 1 < min_len
        min_len = right - left + 1
        min_left = left
      end
      
      # Remove leftmost character
      window_counts[s[left]] -= 1
      if pattern_freq.key?(s[left]) && 
         window_counts[s[left]] < pattern_freq[s[left]]
        formed -= 1
      end
      left += 1
    end
  end
  
  min_len == Float::INFINITY ? "" : s[min_left, min_len]
end

min_window_substring("ADOBECODEBANC", "ABC")
# => "BANC"

Performance Considerations

The two pointers technique achieves time complexity improvements by reducing nested iterations to single passes. Understanding when these improvements apply determines appropriate usage.

Time Complexity Analysis

Most two pointer algorithms execute in O(n) time, where n represents the input size. Each element is examined at most twice—once when a pointer reaches it and possibly once when the other pointer crosses it. This contrasts with brute force approaches requiring O(n²) time to check all pairs.

# Brute force pair sum: O(n²)
def two_sum_brute_force(arr, target)
  arr.each_with_index do |num1, i|
    ((i + 1)...arr.length).each do |j|
      return [i, j] if num1 + arr[j] == target
    end
  end
  nil
end

# Two pointers pair sum: O(n)
def two_sum_optimized(arr, target)
  left = 0
  right = arr.length - 1
  
  while left < right
    sum = arr[left] + arr[right]
    return [left, right] if sum == target
    sum < target ? left += 1 : right -= 1
  end
  nil
end

For sorted input, the preprocessing sort operation dominates at O(n log n). When input is already sorted or when sorting is required anyway, two pointers add only O(n) to the total complexity.

Space Complexity Optimization

Two pointers implementations typically use O(1) auxiliary space, storing only pointer variables and temporary values. This advantage becomes significant when processing large datasets where O(n) space for hash tables or additional arrays proves prohibitive.

In-place modifications using two pointers avoid allocating new arrays. The partition and removal patterns rearrange elements within the original array, returning new length or boundary indices.

Cache Performance

Sequential access patterns in two pointers algorithms exhibit good cache locality. When both pointers move in the same direction, memory access remains sequential. Opposite-end convergence patterns access both ends but still maintain predictable access patterns beneficial for prefetching.

When Two Pointers Underperforms

Two pointers requires specific problem properties to function correctly. For unsorted data where sorting is not acceptable, hash-based solutions often prove faster. When finding all pairs rather than one pair, the O(n²) enumeration becomes unavoidable, though two pointers might still reduce constant factors.

Problems requiring backtracking or exploring multiple paths simultaneously do not fit the two pointers pattern. The technique assumes greedy or deterministic pointer movement rules; when decisions depend on future unknown values, dynamic programming or other approaches apply.

Common Pitfalls

Off-by-One Errors

Incorrect loop termination conditions cause off-by-one errors. The condition left < right versus left <= right depends on whether checking the same element twice is valid.

# Wrong: Misses middle element in odd-length arrays
def buggy_palindrome(arr)
  left = 0
  right = arr.length - 1
  
  while left < right  # Should be left < right for palindrome
    return false if arr[left] != arr[right]
    left += 1
    right -= 1
  end
  true
end

# Correct: Handles all elements
def correct_palindrome(arr)
  left = 0
  right = arr.length - 1
  
  while left < right  # Correct - no need to check middle element
    return false if arr[left] != arr[right]
    left += 1
    right -= 1
  end
  true
end

Infinite Loops

Failing to advance pointers in all code paths creates infinite loops. Each iteration must move at least one pointer closer to termination.

# Buggy: Infinite loop when sum equals target but condition wrong
def buggy_find_pair(arr, target)
  left = 0
  right = arr.length - 1
  
  while left < right
    sum = arr[left] + arr[right]
    if sum == target
      # BUG: No pointer movement
      return [left, right]
    elsif sum < target
      left += 1
    # BUG: Missing else clause for sum > target
    end
  end
  nil
end

Incorrect Pointer Initialization

Starting pointers at wrong positions causes incorrect results or missed elements. Boundary conditions require careful consideration.

# Wrong: Starts second pointer too early
def buggy_pair_sum(arr, target)
  left = 0
  right = arr.length - 2  # BUG: Should be length - 1
  # Misses pairs involving last element
end

# Correct initialization
def correct_pair_sum(arr, target)
  left = 0
  right = arr.length - 1
  # Examines all possible pairs
end

Modifying Array During Iteration

Removing or inserting elements while iterating with indices invalidates pointer positions. Two pointers work with fixed-size arrays or use logical rather than physical removal.

# Dangerous: Physical removal during iteration
def buggy_remove_element(arr, val)
  i = 0
  while i < arr.length
    if arr[i] == val
      arr.delete_at(i)  # BUG: Shifts all elements, invalidates indices
    else
      i += 1
    end
  end
  arr
end

# Safe: Logical removal with write pointer
def safe_remove_element(arr, val)
  write = 0
  arr.each do |element|
    if element != val
      arr[write] = element
      write += 1
    end
  end
  arr[0...write]
end

Handling Empty or Single-Element Arrays

Edge cases with empty or minimal-size inputs require explicit handling or careful boundary checks.

def robust_two_pointer(arr, target)
  return nil if arr.length < 2  # Explicit edge case handling
  
  left = 0
  right = arr.length - 1
  
  while left < right
    # Normal logic
  end
  
  nil
end

Skipping Duplicate Logic

When dealing with duplicates, forgetting to skip them causes incorrect results in problems requiring unique combinations.

# Handles duplicates correctly
def three_sum_no_duplicates(nums)
  nums.sort!
  result = []
  
  nums.each_with_index do |num, i|
    next if i > 0 && num == nums[i - 1]  # Skip duplicate first element
    
    left = i + 1
    right = nums.length - 1
    
    while left < right
      sum = num + nums[left] + nums[right]
      
      if sum == 0
        result << [num, nums[left], nums[right]]
        
        # Skip duplicates for second element
        left += 1 while left < right && nums[left] == nums[left - 1]
        # Skip duplicates for third element
        right -= 1 while left < right && nums[right] == nums[right + 1]
        
        left += 1
        right -= 1
      elsif sum < 0
        left += 1
      else
        right -= 1
      end
    end
  end
  
  result
end

Reference

Pattern Classification

When to Apply Two Pointers

Common Termination Conditions

Complexity Analysis

Ruby Implementation Idioms

Debugging Checklist