Easy Two Pointers Arrays & Strings
In plain English: In a sorted list, find two numbers that add up to a specific target.
In a sorted array, the sum of two pointers tells you which direction to move — too small means the left should increase, too big means the right should decrease.
Prompt
Given sorted array a and target t, return indices of the pair that sums to t.
Try to write it from scratch before scrolling down.
Solution
def two_sum_sorted(a, t):
l, r = 0, len(a) - 1
while l < r:
s = a[l] + a[r]
# sum tells us which pointer to move
if s == t:
return [l, r]
elif s < t:
l += 1
else:
r -= 1
return []
# Test: two_sum_sorted([1,2,3,5,8], 10) == [2, 4]