Two Sum II - Input Array Is Sorted
The shape of the problem
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.