Given a sorted array, find two numbers that add up to a target. The brute force way checks every pair, which is quadratic. The two-pointer trick starts with one pointer at each end and moves them inward: if the sum is too large you move the right pointer left, if it is too small you move the left pointer right. Each number is visited at most once, so the whole thing runs in linear time.
Example: Find two numbers that sum to 10 in a sorted array.
When to use this
→Pair sum / pair with given difference in a sorted array
→Three-sum and k-sum problems (outer loop + two-pointer inner loop)
We want two numbers that add up to the target. Because the array is sorted, we can start with one pointer at each end and squeeze inward instead of trying every pair.
Space play/pause← → stepR replay+ − speed
active line highlighted
1
defpair_sum(arr,target):
2
lo,hi=0,len(arr)-1
3
whilelo<hi:
4
s=arr[lo]+arr[hi]
5
ifs==target:
6
return(arr[lo],arr[hi])
7
elifs>target:
8
hi-=1
9
else:
10
lo+=1
11
returnNone
Quick check
Why does the two-pointer method require the array to be sorted?
What is the time complexity compared to checking every pair?