Two Sum II - Input Array Is Sorted
Given a 1-indexed array sorted in non-decreasing order, return the 1-based positions of the two numbers that add up to a target.
Open on LeetCode ↗Intuition
The trap is the return value before it is the algorithm: this problem is 1-INDEXED, so the hash-map habit from Two Sum I gives you the right pair and the wrong answer. Read the signature and you find the second thing it hands you for free — the array is SORTED, which a hash map throws away by treating the input as an unordered bag. Put a pointer at each end and look at what one comparison buys. If numbers[l] + numbers[r] overshoots, then numbers[l] is the smallest value still in play, so numbers[r] overshoots against every remaining partner — that single comparison retires the whole right column of the pair grid, not one pair. Undershoot and the mirror argument retires the left row. The invariant: the answer, if it exists, always lies strictly inside l..r, so nothing you eliminated could have been it. O(1) space, and remember to return [l+1, r+1].
Approach
Anchor at both ends
Set l to the first index and r to the last. This pair spans the full range of values, so the sum is as adjustable as it will ever be: moving l right can only raise it and moving r left can only lower it. That monotonicity is exactly what sortedness provides, and it is what makes a directed search possible at all.
Steer the sum by one comparison
Compute numbers[l] + numbers[r]. If it equals the target you are done. If it is too small, the only way to increase it is l += 1, because numbers[r] is already the largest available value. If it is too large, r -= 1 for the symmetric reason. Each branch is forced — there is never a choice to make and never a need to backtrack.
Return 1-indexed positions
The problem asks for 1-based indices, so return [l + 1, r + 1]. The loop cannot run past l < r because each step strictly shrinks the window, and the problem guarantees exactly one solution, so the equality branch is always reached before the pointers cross.
Solution & live demo
Edge cases
The first comparison is the only one, and since a solution is guaranteed it must be the answer: return [1, 2].
Nothing changes. The argument depends only on the ordering being non-decreasing, not on the sign of the values.
The two pointers naturally sit on distinct indices, so the constraint that an element cannot be used twice is satisfied without any extra check.
r keeps decreasing until the pointers meet and the loop exits. LeetCode guarantees a solution, but a defensive return of [-1, -1] after the loop documents the case.