Two pointers is a technique where we use two index variables to traverse a data structure, typically an array or string. The pointers move towards each other, away from each other, or in the same direction based on the problem's requirements.

Using this approach, you can reduce the time complexity of many array and string related problems from O(n²) to O(n).

In this chapter, I’ll break down:

What is a Pointer?

Let's first understand what a pointer is.

A pointer is simply a variable that represents an index or position within a data structure, such as an array or linked list.

The pointers can represent:

Using pointers at different positions, we can efficiently compare elements and make decisions without relying on nested loops, which would otherwise lead to O(n²) time complexity.

Variants of Two Pointers

The Two Pointers technique can be applied in different ways depending on the problem.

Let’s explore the three most common strategies.

1. Opposite Direction (Converging Pointers)

The most common variant. One pointer starts at the beginning, the other at the end, and they move towards each other.

The pointers adjust their positions based on comparisons, until a certain condition is met, or they cross each other.

This strategy is ideal for problems where we need to compare elements from opposite ends of an array or string.

Template

The key decision is knowing which pointer to move. In sorted arrays:

Example

Checking if a string is a palindrome

A palindrome is a word, phrase, or sequence that reads the same forward and backward (e.g., "racecar", "madam").

To check if a string is a palindrome, we:

2. Same Direction (Parallel Pointers)

In this approach, both pointers start at the same end (usually the beginning) and move in the same direction at different speeds or for different purposes.

These pointers generally serve two different but complementary roles:

Template

Here are the two popular variations of this approach:

3. Trigger-Based Pointers

In this approach, we move the first pointer independently until it finds an element that meets a certain condition.

After this, we start traversing with the second pointer to find additional information related to what the first pointer found.

This technique is particularly useful when we need to process elements in stages or maintain a fixed distance between two pointers.

Template

A good example of this approach is finding the Nth node from the end of a linked list.

When to use two pointers pattern?

A Two-Pointer algorithm is generally applied to linear data structures, such as: array, strings or linked lists.

A strong clue that a problem can be solved using the Two Pointers technique is if the input data follows a predictable pattern such as sorted array or palindromic string.

It is the right tool when you see these patterns:

1. Sorted array with pair/triplet finding

If the array is sorted (or can be sorted) and you need to find elements that satisfy some relationship, two pointers can often replace nested loops.

2. In-place array modification

When you need to modify an array without using extra space, the read-write pointer pattern is useful.

3. Palindrome or symmetry checking

Comparing elements from both ends naturally leads to two pointers converging.

4. Merging or comparing sorted sequences

When working with two sorted arrays, using a pointer for each is the natural approach.

5. Subarray problems with monotonic conditions

If expanding a window makes a condition "more true" (or "more false") in a predictable way, two pointers can work. This overlaps with sliding window, which is essentially two pointers with specific semantics.

When NOT to use two pointers: