Two Sum II - Input Array Is Sorted
Given a 1-indexed array numbers that is already sorted in non-decreasing order, find the two numbers that add up to a given target. Return their positions as a two-element array [index1, index2] with 1 <= index1 < index2 <= numbers.length — the answer is 1-indexed, not 0-indexed. Exactly one pair is guaranteed to add up to target, and you may not use the same element twice. Solve it using O(1) extra space (beyond the output).
- 2 <= numbers.length <= 3 × 10⁴
- Array is sorted in non-decreasing order
- Exactly one solution exists
- Output positions are 1-indexed
- Must use O(1) extra space
numbers = [2,7,11,15], target = 9[1,2]numbers = [2,3,4], target = 6[1,3]numbers = [-3,-1,0,2,5], target = -1[2,3]We are handed a sorted array and asked to find the two numbers that add up to target, then return their (1-based) positions. It looks a lot like the original Two Sum — but there the array was in random order, and the trick was a hash map that remembered numbers as we went. Here the array is sorted, and that one extra fact unlocks something cleaner and cheaper.
You could just try every pair: fix the first number, then scan everything after it for a partner that completes the target. That is two nested loops — about N²/2 pairs — so O(N²) time. It also completely wastes the gift the problem gave us. The numbers are in order, smallest to largest, and this approach never once uses that.
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i + 1, j + 1]This is the converging two-pointer walk from Valid Palindrome — one marker at each end, moving inward — but with a smarter rule for which end to move. Put left on the first (smallest) number and right on the last (largest). Add them up and compare to the target:
right left.left right to a larger number.left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target:
return [left + 1, right + 1] # 1-indexed positions
elif s < target:
left += 1 # too small — grow the sum
else:
right -= 1 # too big — shrink the sumThe whole thing rests on one argument, so let's actually make it. Suppose nums[left] + nums[right] is too big. Ask: could nums[right] still be part of the answer, paired with some other number? Its partner would have to be one of the numbers between left and right. But nums[left] is the smallest of those — everything else is at least as large. So if even the smallest partner already overshoots the target, every other partner overshoots too. nums[right] can never reach the target with anyone. It is useless, and we can discard it forever by stepping right inward. The mirror argument works when the sum is too small: nums[left] paired with the largest available (nums[right]) still falls short, so it falls short with everyone, and we drop it by stepping left inward. Each step removes exactly one number that we have proven cannot be in the answer — which is why one clean pass finds the pair. The invariant, in plain words: the answer, if it involves any number still inside the left…right window, is still findable there; nothing we discarded could have been part of it.
left=0 (2), right=3 (15). Sum 17 > 9 — too big, so 15 can't work with anyone. right→2.left=0 (2), right=2 (11). Sum 13 > 9 — still too big. right→1.left=0 (2), right=1 (7). Sum 9 — exactly the target. Return [1, 2] (the 1-based positions).Drop this onto the three-slot template from Valid Palindrome. (a) What we read from the two ends: their sum. (b) Which pointer to move: sum too small → left in, too big → right in, equal → done. (c) What to record: nothing until we hit the target, then the two positions. The one and only reason we can decide which end to move is that the array is sorted — order is what turns "the sum is too big" into "so move the big end." Take the sorting away and this steering rule becomes meaningless: in an unsorted array a bigger sum tells you nothing about where a fixing value might sit, and you would be back to a hash map. That is the recognition signal to carry forward — a sorted array plus a question about a pair that hits some target value almost always means this exact inward walk. Next, in 3Sum, we reuse it verbatim as the inner engine, after pinning down one number first.
Two Sum II Visualization
Converging pointers on a sorted array
Crucial Concept
- Monotonic Sum: Moving 'Left' right increases sum. Moving 'Right' left decreases sum.
- Deterministic: At any step, we know exactly which pointer to move based on the sum comparison.
- No Backtracking: Pointers only move in one direction (inward), guaranteeing O(N).
Pattern Recognition
Whenever you need to find a pair in a sorted array, always consider the Two Pointer approach. It almost always beats the O(N) hash map approach in space complexity (O(1) vs O(N)).