visual walkthrough
Two Sum II - Input Array Is Sorted
Sorted input turns Two Sum into an O(1)-space two-pointer scan.
The idea
Because the array is sorted, the sum of the two ends tells you which way to go. If it is too small, the left value can never reach the target (even with the biggest partner), so drop it. If it is too big, drop the right value.
Each step rules out one number for good, so you finish in at most n steps without comparing every pair.
Complexity
| approach | time | space |
|---|---|---|
| Brute force | O(n²) | O(1) |
| Two pointers | O(n) | O(1) |