Two Sum II - Input Array Is Sorted

Problem

Payment processing systems often maintain a sorted list of transaction amounts and need to find two entries that together match a refund target. Given a 1-indexed sorted array of integers and a target sum, return the 1-based indices of the two numbers that add up to the target.

Input: numbers=[2, 7, 11, 15], target=9  → [1, 2]
Input: numbers=[2, 3, 4],      target=6  → [1, 3]
Input: numbers=[-1, 0],        target=-1 → [1, 2]

Solution

Approach: opposite-ends two pointers on a sorted array.

Place left at index 0 (the smallest value) and right at the last index (the largest), then compare numbers[left] + numbers[right] against the target. The sorted order is what makes each move provably safe: if the current sum is too small, the only way to grow it is to pick a larger left value, so advance left inward - numbers[left] can never pair with any value at or below the current right to reach the target, so that position is eliminated. If the sum is too large, the smallest right partner you can still reach is too big, so retreat right. When the sum equals the target you have the answer and return immediately, converting to 1-based indices with [left + 1, right + 1].

Trace [2, 7, 11, 15], target 9: left=0, right=3 gives 2+15=17 > 9, so right--. Now 2+11=13 > 9, right--. Now 2+7=9, a match - return [1, 2]. Each pointer only ever moves toward the other, so every element is touched at most once.

Edge cases: the problem guarantees exactly one solution, so the loop always returns before the pointers meet; the left < right guard prevents reusing one element as both halves of the pair, and negative values work unchanged because the directional logic depends only on sorted order, not sign.

Complexity: O(n) time, O(1) space - the two pointers together make a single inward pass and only two index variables are stored.