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].
The array is sorted, so the sum at the two ends tells you which pointer to move: too small means raise the left, too large means lower the right. No hash map needed — sortedness replaces it, and the space drops to O(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
Common pitfalls
Returning zero-based indices
return [l, r]
return [l + 1, r + 1]
This variant specifies one-based indexing, unlike the original Two Sum. The values are right and the positions are off by one — a bug that passes local reasoning and fails every test.
Moving the wrong pointer
if s < target: r -= 1
if s < target: l += 1
A sum below the target needs a larger value, and the only way to increase it is to raise the left pointer — lowering the right makes the sum smaller still, so the search diverges.
Using a hash map
seen = {}
for i, v in enumerate(numbers):l, r = 0, len(numbers) - 1
Works, but spends O(n) space to rediscover ordering information the input already provides. The follow-up asks for constant space, which the two pointers deliver.
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.