Two pointers is a simple trick that turns a slow search into a fast one. When an array is sorted, you can scan it from both ends at once: one pointer starts on the left, one on the right, and they walk toward each other. Here we use it to solve a classic problem — find two numbers that add up to a target.
Step through the animation on the right. Watch lo and hi start at the two ends and slide inward. The highlighted line of code shows exactly which check is running at each step.
The idea
You have a sorted array and a target sum. You want two values that add up to the target.
The brute-force way is to try every pair — that is O(n²). Two pointers does it in one pass. Put lo at the smallest value and hi at the largest, then look at their sum:
- If the sum is too big, the only way to shrink it is to drop the largest value: move
hileft. - If the sum is too small, you need a bigger number: move
loright. - If the sum is exactly the target, you are done.
Because the array is sorted, each move rules out a value forever — so the pointers only ever move inward, and they meet after at most n steps.
Walk through it
Press Play on the right, or step with Next / Back. The array is [2, 7, 11, 15, 19] and the target is 18. Notice:
- The two cells under
loandhiturn blue when we add them. - If the sum is too big, hi slides one step left. If too small, lo slides one step right.
- When the sum hits the target, both cells turn green — that is the answer.
For this input the pointers land on 7 and 11, which sum to 18.
The code, line by line
def two_sum_sorted(a, target):
lo = 0
hi = len(a) - 1
while lo < hi:
s = a[lo] + a[hi] # sum of the two ends
if s == target: # found the pair
return (lo, hi)
elif s > target: # too big -> shrink from the right
hi -= 1
else: # too small -> grow from the left
lo += 1
return Noneloandhistart at the two ends of the array.- The
whileloop runs until the pointers meet (lo < hi). - Line 5 adds the two ends. Line 6 checks if we found the answer.
- If the sum is too big, line 9 moves
hileft to a smaller value. - If the sum is too small, line 11 moves
loright to a larger value. - If the loop ends without a match, there is no such pair, so we return
None.
Complexity
| Case | Time | Notes |
|---|---|---|
| Best | O(1) (fast) | the two ends already match |
| Average | O(n) (moderate) | one pass, each pointer moves at most n times |
| Worst | O(n) (moderate) | pointers meet in the middle |
O(1) (fast)Why O(n)? Each step moves exactly one pointer inward, and the two pointers cover the array only once before they meet. The space is O(1) because we just keep two index variables — no extra array.
When to use / pitfalls
Reach for two pointers when the input is sorted (or you can sort it first) and you are looking for a pair or a window that meets some condition: two-sum, removing duplicates, reversing in place, or merging two sorted lists. If the array is not sorted and you cannot sort it, a hash set is usually the better tool for two-sum.
This trick only works because the array is sorted. On an unsorted array, moving a pointer does
not reliably make the sum bigger or smaller, so the logic breaks. Sort first (that costs O(n log n))
or use a hash set instead.
Practice
On [2, 7, 11, 15, 19] with target 18, the first check is 2 + 19 = 21. Which pointer moves, and where to?
1. What must be true about the array for this two-pointer method to work?
2. The sum of the two ends is bigger than the target. What do you do?
3. What is the time complexity of the two-pointer scan on a sorted array?
4. The loop ends with lo and hi having met and no match found. What does the function return?