Two Pointer Algorithm Explained

Welcome to my mini-series “Explained” where I will do my best to describe commonly used Data Structures & Algorithms.

Introduction

In this article, we will learn about the Two Pointer algorithm. I will provide a brief overview, give an example, and we will learn how to recognize when to use this technique. I will also mention other variations that two pointers can be used for. Let’s go!

Overview

The Two Pointer algorithm uses two pointers to iterate an array or list until conditions are met. This technique is useful because it allows us to keep track of two values and different indexes in a single iteration. Try using this technique whenever you see a problem that requires you to keep track of two different values in an array. The Two Pointer technique should come to mind.

Fig. Two Pointers

A pointer (see image below) in computer science is a reference to an object. In many programming languages, a pointer is an object that stores a memory address that references a value in computer memory, or in some cases, a memory-mapped computer hardware.

Fig. Pointer Visualized

How do I recognize the pattern?

We want to use the Two Pointer technique because it saves us both time and space. By having two pointers, we can half the time it takes to iterate over the data structure and check the validity of the problem’s conditions.

1. Naive approach using nested loops which has a time complexity of O(n²)
2. Optimized approach using the Two Pointer technique which exploits the symmetric property of palindromes which has a time complexity of O(n)

There are two different approaches to the Two Pointer technique:

1. Pointers at opposite ends of the data structure (at indexes 0 and n)
2. Pointers at the same end of the data structure (at indexes 0 and 1)

Your solution depends on the problem statement. In some instances, we may need to create an additional data structure to iterate over these values. The first approach moves both pointers towards the center after each iteration. The second approach is often referred to as the “Fast & Slow” technique (more details on this in another article).

Fig. Two Pointer Direction Options

The algorithm can be solved generally with the following steps:

1. Initialize two pointers
2. Determine what condition(s) needs to be checked during each iteration
3. Update the pointers
4. Evaluate the values of the pointers

Let’s run through an example

Let’s try a LeetCode example of Valid Palindrome. For example, say you have a string sand want to check if the letters within it are a valid palindrome. Return Trueif it is valid, Falseotherwise.

A palindrome is a sequence that reads the same forward as it does backward.

You could use the Two Pointer technique to solve this problem. *Note that a valid palindrome equals the length of characters in the string and therefore a string with an odd length is invalid.

Example 1:
input: s = “abccba”
output: True 
explanation: “abccba” is a palindrome

Eample 2:
input: s = “abc”
output: False
explaination: “abc” is NOT a palindrome

In this example, we set up two pointers on either end of the string s. Lets refer to Pointer 1 as “left” and Pointer 2 as “right” in the code. Below is a visual followed with the full code and comments.

Fig. Symmetric pointers

# Initialize pointers
left = 0
right = len(s) — 1

# Iterate through all the characters in `s`
while left < right: 
# check that the characters NOT are equal, return False 
  if s[left] != s[right]:
    return False 
# otherwise, the characters are equal, 
# continue to move pointers in by one and compare 
  else:
   left += 1
   right -= 1
return True

Pointers on the same side

Using the example above, it would not make sense to have the pointers at the same end. *Note that both of the pointers could start on either the left or right ends of the array. Please check out my next article “Fast & Slow Technique Explained” for more details.

Fig. Pointers on the same end

Recap

You would want to use a two pointer technique whenever you need to keep track of two elements within an array or list. Important questions to ask yourself to see if we should use a two pointer technique:

• Is the sequence sorted or unsorted?
• Do we need to compare the values of two different indexes?
• Do we need to swap those values?
• Do we need to partition the array?
• Do we want to reduce the number of nested loops?

Varieties

Two pointer problems come in different varieties:

• Binary Search (searching for a sorted array by repetitively splitting in half)
• Symmetric Two Pointers (this example)
• Fast & Slow Pointers (a.k.a. the tortoise & hare algorithm)
• Boundary & Search pointers (one pointer remains the same as the other does a comparison with the other elements in the data structure)
• Sliding Window (a fixed size window using two pointers to search through the data structure)