You are given a 1-indexed array numbers sorted in non-decreasing order and a target. Find two different positions whose values add up to target, and return them as [index1, index2] with 1 <= index1 < index2. Exactly one solution exists, and you must use only constant extra space.
2 + 7 = 9, at 1-indexed positions 1 and 2.- 2 <= numbers.length <= 3 * 10^4
- -1000 <= numbers[i] <= 1000
- numbers is sorted in non-decreasing order
- -1000 <= target <= 1000
- Exactly one answer exists
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Checking all pairs is O(n^2), binary searching the partner of each element is O(n log n), and a hash map is O(n) space. Because the array is sorted, two pointers at the ends give O(n) time and O(1) space: if numbers[l] + numbers[r] is too small, the only way to grow the sum is to move l right; if it is too big, move r left. Each move safely discards one element that cannot be part of the answer.
Algorithm
- Set
l = 0andr = n - 1. - Compute
sum = numbers[l] + numbers[r]. - If
sum == target, return[l + 1, r + 1]. - If
sum < target, dol++; otherwise dor--. Repeat.
O(n)Space: O(1)class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: l, r = 0, len(numbers) - 1 while l < r: s = numbers[l] + numbers[r] if s == target: return [l + 1, r + 1] # 1-indexed if s < target: l += 1 # need a bigger sum else: r -= 1 # need a smaller sum return []