Two Sum II - Input Array Is Sorted
Understand the problem
You're given an ascending sorted integer array numbers (1-indexed). Find two indices i, j (i < j) such that numbers[i] + numbers[j] === target. Return [i, j] using 1-based indices.
Example:
numbers = [2, 7, 11, 15], target = 9
output = [1, 2] // numbers[1-1] + numbers[2-1] = 2 + 7 = 9
numbers = [2, 3, 4], target = 6
output = [1, 3] // 2 + 4 = 6This differs from the original Two Sum in that the array is already sorted — a clear "signal" to use Two Pointers instead of a hash map.
Show the basic approach (slower)
O(n²) time, O(1) spacefunction twoSumSorted(numbers: number[], target: number): [number, number] {
for (let i = 0; i < numbers.length; i++) {
for (let j = i + 1; j < numbers.length; j++) {
if (numbers[i] + numbers[j] === target) return [i + 1, j + 1]
}
}
return [-1, -1] // can't happen per the problem statement
}Two nested loops ignore the "array is sorted" information entirely.
That is the cue to use Two Pointers and take advantage of the sorted order.
Optimal solution
O(n) time, O(1) spacefunction twoSumSorted(numbers: number[], target: number): [number, number] {
let left = 0
let right = numbers.length - 1
while (left < right) {
const sum = numbers[left] + numbers[right]
if (sum === target) return [left + 1, right + 1]
if (sum < target) left++ // need a bigger sum → move left rightward
else right-- // need a smaller sum → move right leftward
}
return [-1, -1]
}This is the optimal approach for a sorted array: one pointer at the start and one at the end.
- If the sum is too small → move the left pointer up; if the sum is too large → move the right pointer down.
- Each step eliminates at least one element, so O(n) steps overall.
Step-by-step trace
1function twoSumSorted(numbers: number[], target: number): [number, number] {2 let left = 03 let right = numbers.length - 14 while (left < right) {5 const sum = numbers[left] + numbers[right]6 if (sum === target) return [left + 1, right + 1]7 if (sum < target) left++ // need a bigger sum → move left rightward8 else right-- // need a smaller sum → move right leftward9 }10 return [-1, -1]11}Edge cases to remember
Two-element array — left=0, right=1, a single check is enough to get it right.
Negative elements: numbers=[-3, -1, 0, 2, 3], target=0 → Two Pointers still works.
The answer pair sits side by side: numbers=[2, 3, 3, 5], target=6 → the two pointers narrow in, meet the 3+3 pair in the middle and return their indices.
The problem guarantees a solution exists — but the code should still return a sentinel value to keep TypeScript happy.