In Phase 2 you solved Two Sum with a hash map. When the input is sorted, there is an even leaner approach that uses two indices and no extra memory.
Given a list numbers sorted in non-decreasing order and an integer target, return the 0-based indices [i, j] with i < j of the two numbers that add up to target. Each input has exactly one solution.
Examples
Input: numbers = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: 2 + 7 == 9
Input: numbers = [2, 3, 4], target = 6
Output: [0, 2]
Constraints
2 <= len(numbers) <= 10**4- Exactly one valid pair exists.
- Aim for O(n) time and O(1) extra space (no hash map needed).
Goals
- Start pointers at opposite ends and move them towards each other
- Use the sorted order to decide which pointer to move
- Solve a pair-finding problem in O(n) time and O(1) extra space