Introduction to Two Pointers

About the pattern

The two pointers pattern is a versatile technique used in problem-solving to efficiently traverse or manipulate sequential data structures, such as arrays or linked lists. As the name suggests, it involves maintaining two pointers that traverse the data structure in a coordinated manner, typically starting from different positions or moving in opposite directions. These pointers dynamically adjust based on specific conditions or criteria, allowing for the efficient exploration of the data and enabling solutions with optimal time and space complexity. Whenever there’s a requirement to find two data elements in an array that satisfy a certain condition, the two pointers pattern should be the first strategy to come to mind.

The pointers can be used to iterate through the data structure in one or both directions, depending on the problem statement. For example, to identify whether a string is a palindrome, we can use one pointer to iterate the string from the beginning and the other to iterate it from the end. At each step, we can compare the values of the two pointers and see if they meet the palindrome properties.

The naive approach is to create a reversed copy of the string and then compare it with the original. This requires creating an additional string of length n, resulting in $O(n)$ auxiliary space. Depending on how the reversed string is constructed, repeatedly creating new strings can also lead to $O(n^2)$ time complexity.

A more efficient approach is to use two pointers, one starting from each end of the string and moving toward the middle. This exploits the symmetry property of palindromes and allows us to compare corresponding characters directly without creating a reversed copy. The pointers together traverse the string once, resulting in $O(n)$ time complexity and $O(1)$ auxiliary space.

Examples

The following examples illustrate some problems that can be solved with this approach:

1. Reversing an array: Given an array of integers, reverse it in place.

2. Pair with given sum in a sorted array: Given a sorted array of integers, find a pair in the array that sums to a number T.

Does your problem match this pattern?

Yes, if all of these conditions are fulfilled:

• Linear data structure: The input data can be traversed in a linear fashion, such as an array, linked list, or string.

• Process pairs: Process data elements at two different positions simultaneously.

• Dynamic pointer movement: Both pointers move independently of each other according to certain conditions or criteria. In addition, both pointers might move along the same or two different data structures.

Real-world problems

Many problems in the real world use the two pointers pattern. Let’s look at an example.

• Photo or video deduplication: In a photo or video gallery application, duplicate files can be efficiently removed using the two pointers pattern when the data is sorted (for example, by file hash). One pointer iterates through each item in the list to examine whether it is a duplicate, while the other pointer keeps track of the position where the next unique item should be placed. As the scanning pointer moves forward, only non-duplicate items are written to the position indicated by the second pointer, effectively compacting the list in place. This approach avoids the need for extra memory and ensures efficient deduplication with a single pass through the data.

Strategy time!

Match the problems that can be solved using the two pointers pattern.

Note: Select a problem in the left-hand column by clicking it, and then click one of the two options in the right-hand column.