How two pointers works
The two-pointer technique keeps two indices into the same array and moves each one in a single direction only. Because neither pointer ever goes back, the two of them together make at most about n moves, where checking every pair would take n(n − 1)/2 checks.
The classic case, and the one animated here: in a sorted array, find two numbers that add up to a target. Put left (L) on the smallest value and right (R) on the largest, and look at their sum.
Think of a gift card worth exactly ₹500 and a shelf of items sorted by price. Pick up the cheapest and the dearest. If together they cost more than ₹500, the dearest item is too expensive to pair with anything on the shelf, even the cheapest, so put it back. If they cost less, the cheapest item cannot reach ₹500 even with the dearest, so put that one back. Every check rules out one item for good.
That is why the method never misses an answer: a pointer only moves past a value that cannot be in any pair with the values still in range. When the two pointers meet, every value has been ruled out, and there is no pair.
The same idea comes in other shapes. Pointers at both ends also reverse an array or check a palindrome. Pointers moving the same way at different speeds remove duplicates from a sorted array in place, or detect a cycle in a linked list. And two pointers that mark the ends of a range are the sliding window.
The algorithm in 5 steps
- 1 Set
left = 0andright = n − 1. - 2 While
left < right, computes = a[left] + a[right]. - 3 If
sequals the target, return[left, right]. - 4 If
sis too small, moveleftone step right; if it is too big, moverightone step left. - 5 If the pointers meet, no pair works: return
[-1, -1].
Worked example
Here is every pair the code checks on a fixed sorted array, generated by the same code as the visualizer. The pointer moves in between are counted in the total but not listed.
Input: [-4, -1, 0, 3, 5, 9, 12], target sum4
- Step 1 Find two numbers that add up to 4. L (left) starts at the smallest value, index 0; R (right) at the largest, index 6. -4-1035912
- Step 2 a[0] + a[6] = -4 + 12 = 8. -4-1035912
- Step 3 8 > 4: too big. Even with the smallest value left (-4), 12 overshoots, so 12 is in no pair. Move R left. -4-1035912
- Step 5 a[0] + a[5] = -4 + 9 = 5. -4-1035912
- Step 6 5 > 4: too big. Even with the smallest value left (-4), 9 overshoots, so 9 is in no pair. Move R left. -4-1035912
- Step 8 a[0] + a[4] = -4 + 5 = 1. -4-1035912
- Step 9 1 < 4: too small. Even with the biggest value left (5), -4 falls short, so -4 is in no pair. Move L right. -4-1035912
- Step 11 a[1] + a[4] = -1 + 5 = 4. -4-1035912
- Step 12 4 is the target. Found the pair: indices 1 and 4 (-1 + 5 = 4). -4-1035912
Result: [1, 4] (-1 + 5 = 4), after checking 4 pairs with 3 pointer moves, out of 21 possible pairs. With target 6 on the same array, the pointers meet after 6 pair checks and return [-1, -1]: no two of these numbers add up to 6.
Time and space complexity
Best
O(1)The smallest and the largest value already add up to the target.
Average
O(n)Every check either finds the pair or moves one pointer inwards, so the work grows in step with the array.
Worst
O(n)At most n − 1 sums: each one rules out a value, and the loop stops when one value is left.
Space
O(1)Just the two indices and the sum. If the input arrives unsorted, sorting it first costs O(n log n).
- Needs sorted input:
- Yes
- Pair checks:
- At most n − 1
- Returns:
- Index pair or [-1, -1]
- Extra memory:
- None
On the 10 numbers in the visualizer, checking every pair means 45 sums. The two pointers checked 6 pairs with 5 pointer moves, and can never need more than 9. For 1,000 numbers the gap is 499,500 pairs against at most 999.
When to use it, and when not to
Good fit
- Pair problems on sorted data: a pair with a given sum, the pair closest to a target, or counting pairs below a limit.
- Triplets after sorting: 3Sum fixes one value and runs two pointers on the rest, O(n²) instead of O(n³).
- Rewriting an array in place: removing duplicates from a sorted array, moving zeros to the end, or partitioning around a pivot, as in <a href="/algorithms/sorting/quick-sort/">quick sort</a>.
- Walking two sorted lists together, as in the merge step of <a href="/algorithms/sorting/merge-sort/">merge sort</a> or finding the common elements of two sorted arrays.
Pick something else when
- The array is unsorted and you must return the original indices (LeetCode 1, Two Sum). Sorting loses the indices; one pass with a hash map answers it in O(n).
- Moving a pointer does not push the answer one predictable way. The method relies on "left up means sum up, right down means sum down", which only holds on sorted data.
- You need every pair, not one. With many duplicates the number of matching pairs can itself be about n²/2, and no pointer trick avoids listing them.
Common mistakes and bugs
-
1.while left <= right
With
<=, the loop can checka[i] + a[i]and pair a value with itself. On[1, 3]with target 6 it reaches left = right = 1 and returns[1, 1], because 3 + 3 = 6. Two different elements needleft < right. -
2.Running it on unsorted input
Nothing in the code checks the order. On
[8, 1, 5]with target 6 the first sum is 8 + 5 = 13, too big, so it drops 5 and then 1, and reports no pair, even though 1 + 5 = 6. Sort first, or use a hash map. -
3.Moving both pointers after a miss
Only one value is proven useless per check. Moving both at once skips pairs: the value you moved past on the other side might have been half of the answer.
-
4.Duplicate answers in 3Sum
After a match, or when the fixed value repeats, skip over equal neighbours. Without that,
[-1, -1, 0, 1, 2]reports the triplet (-1, 0, 1) twice. -
5.Overflow in the sum
In Java, C and C++,
a[left] + a[right]can overflow a 32-bit int when both values are near 2³¹. Compute it as along, or comparea[left]withtarget − a[right]instead. Python integers do not overflow.
Interview questions
Try answering before you open the model answer.
Q1 Prove that the two-pointer pair search never misses a valid pair.
Model answer: Suppose a pair (i, j) with i < j adds up to the target. A pointer can only skip one of them by moving past it. If left moves past i, it is because a[i] + a[right] < target with right >= j, and since the array is sorted a[i] + a[j] <= a[i] + a[right] < target, a contradiction. The same argument with the inequality flipped covers right moving past j. So both pointers reach i and j and the sum is found.
Q2 Solve 3Sum: find all unique triplets that add up to zero.
Model answer: Sort the array. For each index i, run two pointers on i + 1 .. n − 1 looking for a sum of −a[i]. On a match, record it and move both pointers past equal values; also skip i when a[i] equals a[i − 1]. Sorting is O(n log n) and the loops are O(n²), so O(n²) overall with O(1) extra space besides the output.
Q3 Container With Most Water: pick two lines that hold the most water.
Model answer: Start with the two outer lines. The area is min(h[l], h[r]) × (r − l). Move the pointer at the shorter line inwards: moving the taller one can only shrink the width while the height stays capped by the shorter line, so it can never help. Track the best area. One pass, O(n).
Q4 Remove duplicates from a sorted array in place and return the new length.
Model answer: Use a slow pointer w for the next write position and a fast pointer r that scans. Start w = 1; for r from 1 to n − 1, if a[r] differs from a[w − 1], write a[w] = a[r] and increment w. Return w. Each element is read once: O(n) time, O(1) space.
Q5 Two Sum on an unsorted array: two pointers or a hash map?
Model answer: A hash map. One pass storing value → index answers it in O(n) time and keeps the original indices. Two pointers would need a sort first, O(n log n), and extra work to map back to original positions. Two pointers win when the data is already sorted and memory matters.
Frequently asked questions
What is the two-pointer technique?
A way to scan an array with two indices instead of a nested loop. Each pointer moves in one direction only, so together they make at most about n moves. The best-known use is finding a pair with a given sum in a sorted array, with one pointer at each end moving inwards, in O(n) time and O(1) extra space.
Does the two-pointer technique need a sorted array?
For pair-sum problems, yes: moving left up must raise the sum and moving right down must lower it, which is only guaranteed on sorted data. Other two-pointer patterns, such as reversing an array or the fast and slow pointers that detect a linked-list cycle, work on any order.
What is the time complexity of the two-pointer technique?
O(n) for the scan itself, because each step moves a pointer and neither pointer ever moves back. On the pair-sum problem that means at most n − 1 sums. If the input has to be sorted first, the total becomes O(n log n), and the extra space is O(1) apart from the sort.
What is the difference between two pointers and a sliding window?
A sliding window is a two-pointer pattern where both pointers move the same way and mark the two ends of a range, such as a run of numbers whose sum you track. The pair-sum version here has the pointers start at opposite ends and move towards each other, and only the two values they point at matter.
Is two pointers better than binary search for a pair sum?
Usually. On a sorted array you could binary search for target − a[i] for every i, which is O(n log n). Two pointers solve the same problem in O(n) with simpler code. Binary search wins only when you look up one value many times without re-scanning.