Two Pointers · 055Medium
Two Sum II - Input Array Is Sorted
Given a 1-indexed array numbers sorted in non-decreasing order, find two numbers that add up to target and return their 1-based indices [index1, index2] with index1 < index2. You must use O(1) extra space.
Constraints
- 2 <= numbers.length <= 3 * 10^4
- -1000 <= numbers[i] <= 1000
- Exactly one solution exists; numbers is sorted ascending.
- You must use only constant extra space.
Examples
twoSum([2, 7, 11, 15], 9) -> [1, 2] // 1-INDEXED twoSum([2, 3, 4], 6) -> [1, 3] twoSum([-1, 0], -1) -> [1, 2] twoSum([1, 2, 3, 4, 4, 9, 56, 90], 8) -> [4, 5] // the pair is two equal values twoSum([0, 0, 3, 4], 0) -> [1, 2] // zeros twoSum([-1000, -1, 0, 3], -1000) -> [1, 3] // negative target
Edge cases
- The answer is 1-indexed — a classic off-by-one trap.
- Negative values.
Show the target complexity (spoiler)
- Naive
- O(n) time, O(n) space — the hash map from Two Sum, which violates the O(1) space
- Target
- O(n) time, O(1) space — two pointers at the ends; move left in when the sum is too small, right in when too large.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/02-two-pointers/055-two-sum-ii-input-array-is-sorted.js ./practice c 055