Problem Statement
Two Sum II - Input Array Is Sorted
You are given a list of numbers that is already sorted from smallest to largest. You are also given a target number. Your job is to find the two numbers in the list that add up to that target, and return their positions. One small twist: the positions are counted starting from 1, not 0. So the first number is at position 1, the second at position 2, and so on. You also need to return them in order, with the smaller position first. Because the list is sorted, we can be clever and solve this fast, in one pass, without building any extra lookup tables.
Translate the prompt
Given a sorted array and a target, find two indices whose values sum to the target. Sorted is the key asset — do not throw it away.
Signals to notice
Brute force first
Nested loops over every pair: O(n²) time, O(1) space. Ignores the sorted ordering entirely.
The key insight
Because the array is sorted, the smallest possible sum is (first + last-smallest) and the largest is (last + first-largest). Moving the left pointer right strictly increases the sum; moving the right pointer left strictly decreases it. Every move rules out exactly one row or column of the n×n pair space.
Trace it on nums=[2,7,11,15], target=9
l=0 r=3 → 2+15=17 > 9 → r-- l=0 r=2 → 2+11=13 > 9 → r-- l=0 r=1 → 2+ 7= 9 ✓ → return [1,2]
What must stay true
No pair strictly outside the [left, right] window has been skipped yet. Every valid answer is still reachable between the two pointers.
Shape of the loop
l, r = 0, n-1 while l < r: s = nums[l] + nums[r] if s == target: return [l+1, r+1] elif s < target: l += 1 else: r -= 1
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Moving both pointers when only one direction is needed. If sum < target you must move left up; moving right down makes the sum even smaller and you can miss the answer.