The problem
Given an array numbers sorted in non-decreasing order and a target, find the two numbers that add up to target and return their positions, counting from 1, as [index1, index2] with index1 < index2.
There is exactly one answer, you may not use an element twice, and you may use only constant extra space.
Examples
- Input
numbers = [2, 7, 11, 15], target = 9
- Output
[1, 2]
- Input
numbers = [2, 3, 4], target = 6
- Output
[1, 3]
Constraints
- 2 ≤ numbers.length ≤ 3 × 10⁴
- −1000 ≤ numbers[i], target ≤ 1000
- Exactly one solution exists.
The idea
The order is the clue. Take the smallest and the largest: l at the start and r at the end. If their sum is too small, the only way to raise it is a bigger left number — l moves right. Too big, and r moves left.
Each move rules out one number for good: if numbers[l] + numbers[r] is too small, then numbers[l] plus anything is too small, since numbers[r] was the largest left. So the pointers meet the answer in at most n steps, with no extra memory.
- Time
- O(n)
- Space
- O(1)
Solution · every language run against every case
class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: l, r = 0, len(numbers) - 1 while l < r: total = numbers[l] + numbers[r] if total == target: return [l + 1, r + 1] # the answer is 1-indexed if total < target: l += 1 # need a bigger sum: move the small end up else: r -= 1 # need a smaller sum: move the big end down return []