Given a sorted array, find two numbers that add up to a target — how do you do it in O(n) without extra space?

How to think about it

Recognise the pattern

The signal here is sorted input + “find a pair”. Whenever the array is already sorted and you’re looking for two elements that satisfy some condition (sum, difference, product), the two-pointer technique is almost certainly the right tool. You don’t need a hash map — the ordering gives you free navigation.

Build the approach step by step

Brute force loops over every pair (i, j) where j > i, checking if nums[i] + nums[j] == target. That’s O(n²) time and O(1) space. It works, but it ignores the sort entirely.

The insight: if the current sum is too large, the only way to make it smaller is to move the right pointer leftward (toward smaller values). If the sum is too small, move the left pointer rightward (toward larger values). You never need to backtrack, so both pointers travel at most n steps combined — giving O(n) total.

Walk through [2, 7, 11, 15], target 9:

• left=0 (2), right=3 (15) → sum 17, too big → right moves to index 2
• left=0 (2), right=2 (11) → sum 13, too big → right moves to index 1
• left=0 (2), right=1 (7) → sum 9 ✓ → return indices

Complexity

• Time — O(n): each pointer moves at most n steps in total across the entire loop.
• Space — O(1): only two index variables, regardless of input size.

The trap and a pointer diagram