Basics of Two Pointers Technique

What is a pointer?

In this technique, the pointer represent either the index or iteration attribute in an array.

When you loop an array, you can view the index that you’re tracking in every loop as a pointer. A pointer helps us to keep track of the current position, which helps deal with array-related problems.

Loop with one pointer

i = 0 
while i < array.length
   puts array[i]
   i += 1
end

Two pointers

Two-pointers is a useful and effective technique typically used to solve problems involving collections such as arrays. Usually, we use it to keep track of array or string indices with the benefit of optimizing runtime or saving space.

Some common use cases:

• Reverse direction — one starts from the beginning, another from the end.

Reverse Pointers

• Same direction — one with a slower pace, another runs faster

fast-slow pointers

Example: Reverse direction pointers

A classic exercise is the problem of judging palindrome strings. Given a string to determine whether the string is a palindrome.

"abcba" # return true
"abcda" # return false

Reverse direction pointers can easily solve it.

valid palindrome

invalid palindrome

# @param {String} x
# @return {Boolean}
def is_palindrome(x)
  left = 0
  right = x.length - 1
    
  while left < right
    return false if x[left] != x[right]
     left += 1
     right -= 1
  end
  true
end

Example: Same direction pointers

Remove duplicates in an array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

from https://leetcode.com/problems/remove-duplicates-from-sorted-array/

[1, 2, 2, 3, 3, 4] => [1, 2, 3, 4 ,?, ?]

The problem can also be solved by creating a hash and check if the same number exists. However, that’s additional O(n) space.

Without additional space, another idea is to divide the array into 3 sections by 2 pointers and manipulate in place:

• Pointer A (slow)— Always point on the last number of current unique part
• Pointer B (fast) — Loop through array and check duplicate

Hard to imagine? Let’s see how the algorithm works visually:

def remove_duplicates(nums)
  return nums.length if nums.length <= 1
  left = 0
  right = 0
  while right < nums.length
    if nums[left] != nums[right]
      left += 1
      nums[left] = nums[right]
    end
    right += 1
  end
  return left + 1
end

Note: The solution only works when given a sorted array which ensured to find a unique number when comparing left and right pointers.

Why and How

Two-pointer is just a tool or strategy to solve problems. The main idea is to iterate two different parts of the array simultaneously to solve the problem efficiently.

While we are manipulating the array in place, this approach works in constant space. Like most algorithm problems, there are usually multiple ways to solve them. The two-pointer technique appears to be a good starting point for optimization when dealing with an array or list problems.

Here are some thoughts to follow when you are implementing the two-pointer approach, depends on what you are trying to achieve:

• Pointers Initializing — Your starting points. The indexes that you want to compare with.
• Movement Judging — The movement affects the coverage of comparison. There should be a solid condition to judge the pointer’s movement whether to move forward or pause.
• Stop condition — condition to stop the pointer movement. Usually stops at the end of array iteration or when two-pointer meet intersection.

More Followup Problems

• Valid Palindromes — only alphabet & numbers
• Valid Palindromes II — allow delete one character
• Two Sum
• Sliding Window
• Two Difference — Two Sum difference equal to target
• Middle of Linked List
• Linked List Cycle

References

AlgoDaily - Using the Two Pointer Technique - Introduction

Two Pointers Technique - GeeksforGeeks

Two-Pointer Technique: Solving Array Problems at Light Speed

Two Pointers Approach — Python Code

All images were created by the author.