165. Two Sum II - Input Array Is Sorted
You receive an array of integers numbers that is already sorted in non-decreasing order, plus an integer target. Somewhere in the array sit two distinct elements whose sum is exactly target — find them and return their positions as a pair (i, j) with i < j.
Two twists versus the classic Two Sum: positions here are 1-indexed (the first element is position 1), and every input is guaranteed to contain exactly one valid pair, so there is never a tie to break. You may not add an element to itself, though two equal values at different positions are fair game.
The sorted order is the whole point of this variant: aim for a solution that uses constant extra memory — the hash map from Two Sum I works, but it is not the lesson here.
Example 1:
Input: numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]
Explanation: numbers[1] + numbers[2] = 2 + 7 = 9 (1-indexed), so the answer is positions 1 and 2.
Example 2:
Input: numbers = [2, 3, 4], target = 6
Output: [1, 3]
Explanation: 2 + 4 = 6. Note that 3 + 3 is not allowed — the same element cannot be used twice.
Example 3:
Input: numbers = [-1, 0], target = -1
Output: [1, 2]
Explanation: -1 + 0 = -1, the only pair available.
Constraints:
- 2 ≤ numbers.length ≤ 3 * 10⁴
- -10⁹ ≤ numbers[i] ≤ 10⁹
- numbers is sorted in non-decreasing order
- -10⁹ ≤ target ≤ 10⁹
- Exactly one pair of positions is a valid answer.
Hints:
The array is sorted — that should immediately suggest either binary search or a pointer at each end.
For each element x, its partner target − x can be found with a binary search over the elements to its right. That is O(n log n) with no extra memory.
Better: put one pointer at each end. If the two values sum too high, only moving the right pointer left can help; too low, only moving the left pointer right can. Each step safely discards one element, so the scan is O(n).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: numbers = [2, 7, 11, 15], target = 9
Expected output: [1, 2]