#167
Two Sum II - Input Array Is Sorted
Medium Opposite ends
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
In a sorted (1-indexed) array, find the two positions whose values add up to target. Use only constant extra space.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: two numbers in a sorted array that add up to target.
Why this works: start with smallest + largest. Too small? Only moving left up can help. Too big? Only moving right down can help.
Example: [2, 7, 11, 15], target 9
2 + 15 = 17 too big → r--2 + 11 = 13 too big → r--2 + 7 = 9 ✓ → [1, 2]
✦Hints open one at a time
Start with the smallest and largest values.
Sum too small? Move the left pointer right. Too big? Move the right pointer left.
↗Approach
Two pointers from both ends. Because the array is sorted, each move safely discards one value that can't be part of the answer.
</>Solution (Java)
class Solution {
public int[] twoSum(int[] numbers, int target) {
int l = 0, r = numbers.length - 1;
while (l < r) {
int sum = numbers[l] + numbers[r];
if (sum == target) return new int[]{l + 1, r + 1};
if (sum < target) l++;
else r--;
}
return new int[0];
}
}!Common mistake
Returning 0-based indexes — this problem wants 1-based ones.
Complexity
- Time: O(n).
- Space: O(1).
