When an array is already sorted, two pointers can find a pair that meets a condition in O(n) time and O(1) space — no hash map needed.
Use when: the input is sorted (or can be sorted) and you need to find a pair satisfying a constraint.
Place one pointer at the start and one at the end. The sorted order tells us which pointer to move: - Sum too small? Move left pointer right (increase sum) - Sum too large? Move right pointer left (decrease sum)
Because the array is sorted, moving lo right
increases the sum, and moving hi left
decreases it. This is what makes the technique
work — we always know which direction to go.
Trace: sorted = [1, 3, 5, 7, 9], target = 8
lo=0(1), hi=4(9): sum=10 > 8, hi– lo=0(1), hi=3(7): sum=8 == 8, found! return (0, 3)
func pairSum(sorted []int, target int) (int, int, bool) {
lo, hi := 0, len(sorted)-1
for lo < hi {
sum := sorted[lo] + sorted[hi]
if sum == target {
return lo, hi, true
}
if sum < target {
lo++
} else {
hi--
}
}
return 0, 0, false
}
func main() {
i, j, found := pairSum([]int{1, 3, 5, 7, 9}, 8)
fmt.Printf("indices: (%d, %d), found: %v\n", i, j, found)
i, j, found = pairSum([]int{2, 4, 6, 8}, 10)
fmt.Printf("indices: (%d, %d), found: %v\n", i, j, found)
_, _, found = pairSum([]int{1, 2, 3}, 10)
fmt.Printf("found: %v\n", found)
}