Two Sum II Input Array Is Sorted#

Given a sorted array of integers in non-decreasing order and a target value, find the two numbers that add up to the target. Return their 1-based positions. There is exactly one solution and you may not use the same element twice.

Example#

Input: numbers = [2, 7, 11, 15], target = 9 Output: [1, 2] because numbers[0] + numbers[1] == 9, returned as 1-based indices.

Brute force#

Try every pair of positions with two nested loops. This ignores the fact that the array is already sorted.

• Time: O(n^2).
• Space: O(1).

Optimal approach#

Because the array is sorted, use two pointers starting at the ends. Look at the sum of the two pointed values. If the sum is too small, move the left pointer right to increase it. If the sum is too large, move the right pointer left to decrease it. If the sum matches the target, return the 1-based positions. The sorted order guarantees you never skip a valid pair.

Python solution#

 1def two_sum(numbers, target):
 2    left, right = 0, len(numbers) - 1
 3    while left < right:
 4        total = numbers[left] + numbers[right]
 5        if total == target:
 6            return [left + 1, right + 1]
 7        if total < target:
 8            left += 1
 9        else:
10            right -= 1
11    return []

Complexity#

• Time: O(n), each pointer moves inward at most n steps total.
• Space: O(1), only two indices.

This problem is the sorted-array two-pointer technique at its cleanest. Keep going with the 60-day challenge.