You're given an array of integers, sorted in increasing order, and a target. Find the two numbers that add up to the target, and return their positions, counting from 1. There is exactly one answer, and you may only use constant extra space.
DSA Animator › DSA Revision › Arrays › Two Sum II
Remember: in a sorted array, two pointers from both ends find a pair in one pass. Sum too big, move right in. Sum too small, move left in. The video solves Two Sum II (LeetCode 167, Medium) with the Two Pointers pattern from the Arrays topic, and you can replay every step in the interactive Two Sum II animation.
You're given an array of integers, sorted in increasing order, and a target. Find the two numbers that add up to the target, and return their positions, counting from 1. There is exactly one answer, and you may only use constant extra space.
For 1, 3, 4, 5, 7, 10 and 11, with target 9, the answer is positions 3 and 4. That's 4 plus 5, which makes 9.
The brute force checks every pair, which is O of n squared. A hash map gets it down to O of n time, but it needs O of n extra space, and that's not allowed here. Neither one uses the fact that the array is sorted.
Put one pointer at the start and one at the end. If their sum is too big, the right number is too large, so move the right pointer left. If the sum is too small, move the left pointer right. Every move throws away a number that can never be part of the answer.
Start with left on 1 and right on 11. 1 plus 11 is 12, which is too big, so right moves to 10. 1 plus 10 is 11, still too big, so right moves to 7. 1 plus 7 is 8, too small, so left moves to 3. 3 plus 7 is 10, too big, so right moves to 5. 3 plus 5 is 8, too small, so left moves to 4. 4 plus 5 is 9, which is exactly the target. They sit at indexes 2 and 3, so we return positions 3 and 4.
In code, start the two pointers at both ends. While left is less than right, add the two numbers. If the sum equals the target, return both indexes plus 1. If the sum is smaller, move left forward, otherwise move right back. Each step removes one candidate, so it's O of n time and O of 1 space.
Remember: in a sorted array, two pointers from both ends find a pair in one pass. Sum too big, move right in. Sum too small, move left in.