Two Sum II - Input Array Is Sorted
The integer array numbers is sorted in non-decreasing order and indexed from 1. Find the two entries whose sum equals target and return their positions.
Examples
2 + 7 = 9, and those values sit at positions 1 and 2 counting from 1, so the answer is [1, 2].
2 + 4 = 6, at positions 1 and 3 counting from 1, so the answer is [1, 3].
Problem Understanding
This is similar to the classic Two Sum, but with two key differences:
- The array is already sorted.
- You must return 1-based indices.
A brute force approach would be to check every pair, which is O(n²). However, the sorted property allows us to use the Two Pointers technique to solve it in linear time O(n).
Algorithm Strategy
- Initialize
leftat the start (index 0) andrightat the end (index n-1). - Calculate
current_sum = numbers[left] + numbers[right]. - If
current_sum == target, we found the pair! Return[left + 1, right + 1]. - If
current_sum < target, we need a larger sum. Since the array is sorted, movingleftto the right increases the sum. - If
current_sum > target, we need a smaller sum. Movingrightto the left decreases the sum.
Interactive Visualization
TARGET 9
START AT THE ENDS
L
0
1
2
R
3
Left
0
Right
3
Sum
—
Returns
—
Target 9: left starts at index 0, right at index 3
Next
numbers[0] + numbers[3] = 2 + 15 = 17
Sorted array
Target
Legend & Complexity
The values under L and R being added
The pair that sums to the target
Values outside the pointers: ruled out
Time
O(n)
Space
O(1)
Each step adds the values under L and R and moves one pointer toward the target; values outside the pointers are struck out, because no answer can use them.
Dry Run: nums = [2, 7, 11, 15], target = 9
| Iteration | Left (Index/Val) | Right (Index/Val) | Sum (L+R) | Comparison | Action |
|---|---|---|---|---|---|
| 1 | 0 / 2 | 3 / 15 | 17 | 17 > 9 (Too Big) | Decrement Right |
| 2 | 0 / 2 | 2 / 11 | 13 | 13 > 9 (Too Big) | Decrement Right |
| 3 | 0 / 2 | 1 / 7 | 9 | 9 == 9 (Match!) | Return [1, 2] |
Edge Cases & Common Mistakes
Edge Cases:
- No Solution: Ensure your code handles cases where no pair sums to the target (return empty vector/array).
- Array Constraints: Typically length >= 2.
Common Mistakes:
- 0-based vs 1-based: The problem asks for 1-based indices. Returning
[left, right]instead of[left+1, right+1]is a frequent bug! - Not using Sorted Property: Using a Hash Map (O(n) space) works but is explicitly suboptimal when O(1) space is required.
Solution
Two Sum II - Input Array Is Sorted Code
1/**2 * @param {number[]} numbers3 * @param {number} target4 * @return {number[]}5 */6var twoSum = function(numbers, target) {7 let left = 0;8 let right = numbers.length - 1;910 while (left < right) {11 let sum = numbers[left] + numbers[right];1213 if (sum === target) {14 return [left + 1, right + 1];15 } else if (sum < target) {16 left++;17 } else {18 right--;19 }20 }2122 return [];23};