Approach Summary
With sorted input, use left and right pointers. If sum is too small, advance left. If too large, retreat right.
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
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
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 {};
}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 [];
}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
Master the Two Pointers Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Two Pointers pattern.
How to Recognize This Pattern
- Sorted array
- Find pair with target sum
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)