Problem Statement
Explain the two pointers pattern on a sorted array for finding a pair with a target sum. Compare with the hash map method.
Explanation
With two pointers, place one at the left and one at the right. If the sum is too small, move left forward; if too big, move right backward. This finds a pair in linear time and constant extra space on sorted data.
The hash map method also runs in linear time without sorting, but it uses extra space and does not give sorted order guarantees. If sorting is allowed or already given, two pointers is simpler and more space efficient.
Code Solution
SolutionRead Only
def pair_sum_sorted(a, target):
i, j = 0, len(a)-1
while i < j:
s = a[i] + a[j]
if s == target: return i, j
if s < target: i += 1
else: j -= 1
return None