BeginnerTwo Pointers
Two pointers from both ends of a sorted array
Sorted input and you need a pair? Start at both ends: too small, move left in; too big, move right in. O(n), no extra memory.
The idea
In a sorted array, the smallest is on the left and the largest on the right. Their sum tells you which way to go: too small means you need a bigger left value, so move left forward; too big means a smaller right value, so move right back.
Each step rules out one element for good, so the pointers meet after at most n steps.
Worked example
Two Sum II: numbers = [2, 7, 11, 15], target = 9
- left=2, right=15 → 17 > 9 → move right in
- left=2, right=11 → 13 > 9 → move right in
- left=2, right=7 → 9 → found (positions 1 and 2, 1-indexed)
In code (Python)
def two_sum_sorted(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left + 1, right + 1]
if total < target:
left += 1
else:
right -= 1O(n) time, O(1) space.
How to spot it
- The array is sorted (or you can sort it) and you need a pair or triple with some sum.
Common mistakes
- Using `left <= right`, which can pair an element with itself.
- Applying it to unsorted input without sorting first.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →