The Two-Pointer Pattern
Walk a sorted array from both ends (or at two speeds) to solve pair-sum, dedupe, and reversal problems in one pass and O(1) space.
On this page
The two-pointer pattern is the first one most interviews test, and for good reason: it turns a whole class of O(n²) brute-force solutions into clean, one-pass O(n) ones using no extra space. The idea is simple - use two indices that move toward each other or in the same direction - but knowing when it applies is the skill.
The converging pointers
The classic setup: a sorted array and a target pair. Put one pointer at each end. Look at the sum of the two ends and let it tell you which pointer to move:
- Sum too small? The only way to grow it is to move the left pointer right (to a bigger value).
- Sum too big? Move the right pointer left (to a smaller value).
- Equal? You've found the pair.
Each step rules out one element for good, so the pointers meet after at most n steps.
sum 12 > 10: too big → move right pointer left
Because the array is sorted, moving left can only increase the sum and moving right can only decrease it — so each step rules out no valid pair. One pass, O(n) time and O(1) space, versus the O(n²) nested-loop brute force.
// two-sum on a SORTED array — O(n) time, O(1) space
int[] twoSum(int[] a, int target) {
int lo = 0, hi = a.length - 1;
while (lo < hi) {
int sum = a[lo] + a[hi];
if (sum == target) return new int[]{lo, hi};
if (sum < target) lo++; // need a bigger sum
else hi--; // need a smaller sum
}
return new int[]{-1, -1};
}Why is this correct and not just lucky? Because the array is sorted, moving lo right can only
increase the sum and moving hi left can only decrease it. So when the sum is too small, no pair
using the current lo and a smaller hi could ever reach the target - we can safely discard lo.
That's the invariant that makes it work.
The same-direction variant
Two pointers don't always converge from the ends. A slow/fast pair moving the same direction
solves in-place problems - like removing duplicates from a sorted array, where slow marks the
write position and fast scans ahead:
// remove duplicates in place, return new length — O(n) time, O(1) space
int removeDuplicates(int[] a) {
if (a.length == 0) return 0;
int slow = 0;
for (int fast = 1; fast < a.length; fast++)
if (a[fast] != a[slow]) a[++slow] = a[fast];
return slow + 1;
}Two pointers usually needs sorted input
The converging version relies on order - it's what lets you discard a whole side. If the array isn't sorted, either sort it first (O(n log n), still often worth it) or reach for a hash set instead (O(n) but O(n) space). Recognizing that trade-off - sort + two pointers vs. hashing - is a common interview decision.
Two librarians look for two books whose page counts add up to exactly 500, on a shelf sorted by thickness. One starts at the thin end, one at the thick end. If their two books total too little, the thin-end person steps toward thicker books; too much, the thick-end person steps toward thinner ones. They never backtrack, and they meet in the middle - scanning the shelf once between them instead of each checking every pairing. That coordinated walk is the two-pointer pattern.
Given a string, determine whether it reads the same forwards and backwards, ignoring case (assume letters only for now). Explain how two pointers solve this in one pass and O(1) extra space, and which direction the pointers move.
Why does the converging two-pointer approach require a sorted array for pair-sum?
Key takeaways
- Two pointers turns many O(n^2) brute forces into one-pass O(n), O(1)-space solutions.
- Converging pointers (from both ends) solve pair/triplet problems on sorted arrays; the sum tells you which pointer to move.
- Correctness comes from sorted order: moving left only grows the sum, moving right only shrinks it.
- Slow/fast pointers moving the same direction solve in-place problems like deduping and partitioning.
- If the input isn't sorted, choose between sort + two pointers (O(n log n), O(1) space) and hashing (O(n) time, O(n) space).