Two Sum II – Input Array Is Sorted

Medium

The problem

Given a list of numbers sorted from smallest to biggest and a target, find the two different positions whose numbers add up to the target. Return the two positions as [first, second] with first < second. Positions are counted from 1 here, not from 0.

Example 1
Input: numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]
The first and second numbers are 2 and 7, and 2 + 7 = 9.
Example 2
Input: numbers = [1, 3, 4, 5], target = 8
Output: [2, 4]
3 + 5 = 8, and they are the 2nd and 4th numbers.
Example 3
Input: numbers = [-1, 0], target = -1
Output: [1, 2]
-1 + 0 = -1.

Limits

2 ≤ numbers.length ≤ 100,000
numbers is sorted in non-decreasing order
Exactly one pair adds up to target
The same position cannot be used twice

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

The array is sorted. If the sum is too big, which end is responsible?

The idea

Left at start, right at end. If sum > target move right left; if sum < target move left right; else you found it.

Target: O(n) time, O(1) space

Go function shape

func twoSum(numbers []int, target int) []int

Reference solution

Tested with go test. Try it yourself first, then compare.

// TwoSumSorted: 1-based indices of two numbers in sorted input summing to target.
func TwoSumSorted(numbers []int, target int) []int {
	left, right := 0, len(numbers)-1
	for left < right {
		sum := numbers[left] + numbers[right]
		if sum == target {
			return []int{left + 1, right + 1}
		} else if sum < target {
			left++
		} else {
			right--
		}
	}
	return nil
}

Read the lesson: Two Pointers