Problem: Two Sum When Input Array is Sorted

Let’s try another classic problem: Two Sum When Input Array is Sorted.

So the method signature would be something like this:

public static int[] twoSum(int[] numbers, int target) {

}

Alright, but what does this problem mean? Let’s look at some examples to understand it better.

Example 1:

Suppose the input is numbers = [2,7,11,15] and target = 9. We want to find two numbers in the array that add up to 9. In this case, 2 + 7 equals 9, so we return their indices as [0, 1].

Example 2:

For numbers = [2,3,4] and target = 6, the numbers 2 and 4 add up to 6, so we return their indices as [0, 2].

Example 3:

Given numbers = [-1,0] and target = -1, the numbers -1 and 0 add up to -1, so we return their indices as [0, 1]. This example also shows that the input can contain negative numbers, and our algorithm should handle that correctly.

The convention for this problem is that the input array has at least two elements, so there is no edge case for an empty array. And there is exactly one solution, so you do not have to decide what to do when several pairs add up to the target.

Like the previous problem, I recommend that you first solve this one with a brute-force approach, and then try to optimize it.