Get 2 The Point
The Two Pointers Pattern/Technique
The two pointers pattern optimizes algorithms that handle strings, sorted arrays, or linked lists by using two pointers to keep track of indices, simplify the logic, and save time and space. In this pattern, two pointers iterate through the data structure, in tandem, until one or both of the pointers hit a certain condition.
What’s the point?
This pattern is useful when we need to analyze each element of a collection compared to its other elements.
To solve problems like these, we could start from the first index and loop through one or more times. While a brute force or naive solution with one pointer will work, it will produce something along the lines of O(n²) time complexity. In many cases, two pointers can help you find a solution with better run time or space complexity by processing two elements per loop instead of just one.
Point me in the right direction
The many variations of the two pointers pattern can be classified as either Opposite Directional or Equi-Directional.
- Opposite Directional — the two pointers move in the opposite direction.
- Equi-Directional — the two pointers move in the same direction.
Opposite Directional
One pointer starts from the beginning and the other pointer starts from the end, moving toward each other until they both meet or satisfy a condition.
This pattern is on point when:
- there is a target value to match or duplicates to be removed
- the problem involves sorted arrays (or linked lists), a set of pair elements, a triplet, or even a subarray
- you need to find a set of elements that fulfill certain constraints
Sample Problems
- Sorted Two Sum
- Reverse String
- Valid Palindrome
- Remove Element
- Move Zeroes
- Two Sum II
- Container With Most Water
Example
Equi-Directional (Fast and Slow Pointers)
There are many variations that utilize fast and slow pointers, including: Floyd’s Tortoise and Hare. In general, one pointer (the fast pointer) moves each iteration and the other pointer (the slow pointer) moves with some restrictions. For more complex scenarios, the fast runner also moves with some restrictions.
This pattern is on point when:
- the problem involves something related to cyclic data structures
- you need to know the position of a certain element or the overall length of a linked list
- the problem deals with a loop in a linked list or sorted array
Sample Problems
- Remove Duplicates from Sorted Array
- Find the Duplicate Number
- Happy Number
- Middle of the Linked List
- Linked List Cycle
- Palindrome Linked List
- Longest Substring Without Repeating Characters
- Remove Nth Node From End of List
- Circular Array Loop
Example
📚 Resources 👀
AfterAcademy — What is the Two pointer technique?
Algorithm Templates: Two Pointers — Part 1
