Approach Summary
With sorted input, use left and right pointers. If sum is too small, advance left. If too large, retreat right.
Full Solution & Approach
Because the input is sorted, a pair can be found without a hash map. Place two pointers at the two ends: left at 0 and right at the last index. If numbers[left] + numbers[right] equals the target, return the two 1-based indices. If the sum is smaller than the target, the only way to increase it is to move left right; if larger, move right left. Each step eliminates exactly one candidate index, so the pointers meet after at most n comparisons. This is the canonical two-pointer-on-sorted-array pattern: it relies on monotonicity — a sorted array guarantees that moving left strictly increases the sum and moving right strictly decreases it. The hash-map approach from the unsorted Two Sum still works, but the two-pointer version is the intended solution here and uses no extra space.
The two pointers traverse the array at most once total — O(n) time. Only two index variables — O(1) space.
Solution Code
Solution
def two_sum(numbers: list[int], target: int) -> list[int]:
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left + 1, right + 1]
elif total < target:
left += 1
else:
right -= 1
return []function twoSum(numbers, target) {
let left = 0, right = numbers.length - 1;
while (left < right) {
const total = numbers[left] + numbers[right];
if (total === target) return [left + 1, right + 1];
if (total < target) left++;
else right--;
}
return [];
}public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int total = numbers[left] + numbers[right];
if (total == target) return new int[]{left + 1, right + 1};
else if (total < target) left++;
else right--;
}
return new int[]{};
}vector<int> twoSum(const vector<int>& numbers, int target) {
int left = 0, right = (int)numbers.size() - 1;
while (left < right) {
int total = numbers[left] + numbers[right];
if (total == target) return {left + 1, right + 1};
else if (total < target) left++;
else right--;
}
return {};
}Edge Cases to Watch
- Pair at the two extremes (first and last elements)
- Negative numbers — the monotonic argument still holds
- Exactly one solution is guaranteed — no tie-breaking needed
- Duplicate values — indices are distinct by construction
How to Recognize This Pattern
- Sorted array
- Find pair with target sum
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)