Two Sum II — Sorted Input
Given an array of integers sorted in non-decreasing order and a target, return the 1-based indices of the two elements that sum to the target. Exactly one solution exists and you must use only constant extra space.
- 2 ≤ n ≤ 3 · 10^4
- -1000 ≤ numbers[i], target ≤ 1000
- Exactly one solution
- The array is sorted
- Constant extra space rules out a hash map
- Sum too small → move left up; too large → move right down
When order gives you a way to decide which of two ends to move, you can replace an O(n^2) double loop by a single pass. Opposite-direction pointers exploit sortedness (move the side that must change); same-direction pointers maintain a "written so far" prefix for in-place compaction.
Place one pointer at each end. If the pair sums to the target, return the indices. If the sum is smaller, the left pointer must advance because every pair with the current left element and a smaller right element is even smaller; symmetrically, move the right pointer when the sum is too large. Sortedness guarantees each move discards only pairs that cannot be the answer.
- Binary searching the complement for each element gives O(n log n) with O(1) space; a hash map gives O(n) time but O(n) space.