Two Sum II — Input Array Is Sorted

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers that add up to a specific target.

Return the indices of the two numbers, 1-indexed, as two space-separated integers.

Example

Input: numbers = [2, 7, 11, 15], target = 9 Output: 1 2 (numbers[1] + numbers[2] = 2 + 7 = 9)

Approach

Since the array is sorted, start one pointer at the beginning and one at the end. If the sum is too small, move the left pointer right; if too large, move the right pointer left. This is O(n) instead of the O(n²) brute-force nested loop.

Walkthrough

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

Input format

Line 1: space-separated integers (the array) Line 2: the target integer

Print the two 1-indexed positions, space-separated.