Given a 1-indexed sorted array, return the indexes of the two numbers that add up to the target. Exactly one solution exists; use O(1) extra space.
Before you code
A hash map would work but uses O(n) space. The sorted order lets two pointers rule out a whole row of pairs at every step.
Hints
- Start at both ends.
- Sum too small: move the left pointer right. Too big: move the right pointer left.
- Return 1-based indexes.
Production & complexity notes
When solving Two sum II: input array is sorted on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Two pointers to reinforce the underlying pattern.
What it practices
Why each move is safe, from Two pointers.