In a sorted array, find whether two numbers sum to target using O(1) space.
Options
- Hash set of the numbers seen so far (O(n) space)
- Two pointers from both ends, moving by the sum (Correct option)
- Build a binary search tree from the whole array
- Recursively try every pair of numbers in the array
Answer
Two pointers from both ends, moving inward based on the sum
Why
Put one pointer at the start (smallest) and one at the end (largest).
If their sum is too small, move the left pointer right to get a bigger number. If too big, move the right pointer left. If equal, done.
Because the array is sorted, each move safely discards one candidate: O(n) time, no extra memory.
Remember
Sorted array + pair search → two pointers.