Two Pointers Technique Explained
If you prefer videos, here's a super quick introduction to Two Pointers:
Two pointers is a common interview technique for problems on an iterable structure such as an array or string. As the name suggests, it keeps two positions and moves them through the structure. The pointers do not have to be two separate variables — as long as the second position can be derived from the first, it still counts as two pointers.
"Two pointers" is a broad topic with no single implementation. Most variants share these traits:
- Two moving pointers, whatever their direction, moving together or independently;
- Some check on the entries the two pointers refer to, which relates to the answer;
- A simple rule for deciding which pointer to move next;
- A way to update the answer as the pointers move.
The sections below show three common shapes. Each states a small problem you can grasp in one sentence, then lets you step through it.
Classifications
Same Directions
Here the two pointers move in the same direction, one trailing the other. A simple example: is "ace" a subsequence of "abcde"? — can you find every letter of the first string inside the second, in order (a, then c, then e)?
Walk one pointer through each string. Advance the pointer in the longer string every step; each time its letter matches the current letter of the shorter string, advance that pointer too. If the shorter string's pointer reaches the end, every letter was found in order, so it is a subsequence. Both pointers only ever move forward, and neither string is modified.
Opposite Directions
Here the two pointers start at opposite ends and move toward each other. A simple example: is a word a palindrome? — does it read the same forwards and backwards?
Put one pointer at each end and compare the two letters. If they differ, it is not a palindrome. If they match, move both pointers inward and compare again. When the pointers meet in the middle, every pair matched, so the word is a palindrome.
Two Pointers vs Sliding Window
A sliding window keeps the two pointers a set distance apart and works with all the values between them, not just the two endpoints. The simplest version uses a fixed-size window. For example: what is the largest sum of any k consecutive numbers?
Add up the first k numbers to get the first window's sum. Then slide the window one step at a time: add the number entering on the right and subtract the number leaving on the left. Each move updates the sum in constant time instead of re-adding k numbers, while you track the largest sum seen. Letting the window grow and shrink instead of staying size k handles harder problems like the longest substring without repeating characters.
Non-array Applications
The two-pointer technique is not limited to arrays. It works on any iterable structure, such as a linked list. For example, Linked List Cycle asks you to detect a cycle in a linked list, which can be solved with a two-pointer method called Floyd's Cycle-Finding Algorithm.
Why Use Two Pointers?
Two pointers often replace a naive nested-loop solution. Checking every pair with two loops is O(n^2); a two-pointer scan usually passes through the data once, bringing it down to O(n).