Problem statement

Brute force

This problem is similar to 1. Two Sum, except that the input array numbers is sorted in non-decreasing order.

The simplest way to solve this problem is to check every pair of numbers using two pointers. Since numbers is sorted, then for each numbers[i] for i = 0,...,len(numbers)-1, we linearly search in numbers[i+1:len(numbers)] for numbers[j] such that numbers[i] + numbers[j] == target. In other words, we start the two pointers at the first two elements of numbers and then let the second pointer move faster than the first pointer along the rest of the numbers array.

In Python, this would be implemented as follows:

1
2
3
4
5
6

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)):
            for j in range(i,len(numbers)):
                if numbers[i] + numbers[j] == target:
                    return [i+1, j+1]

However, this would require $O(n^2)$ iterations over the numbers array, where $n$ is the length of the numbers array, and $O(1)$ space. Can we do better?

Because the numbers array is sorted, then for each numbers[i], we search in numbers[i+1:len(numbers)] for numbers[j] using a binary search such that numbers[i] + numbers[j] == target.

Because we use a binary search instead of a linear search, then the number of iterations when searching inside numbers[i+1:len(numbers)] for each numbers[i] will go down from $O(n)$ to $O(\log n)$, such that the total number of iterations goes down from $O(n \cdot n) = O(n^2)$ to $(n \cdot \log n)$. The space required is still $O(1)$.

Believe it or not, we can do even better.

Two pointers on either side

Consider pointers i = 0 and j = len(numbers) - 1 placed at both ends of the numbers array. Then, consider the sum result = numbers[i] + numbers[j].

If pointer i moves to the right by 1, and since numbers is sorted in non-decreasing order, then numbers[i] must increase or stay the same. Hence, result also increases or stays the same.

Similarly, if pointer j moves to the left by 1, then numbers[j] must decrease or stay the same, such that result also decreases or stays the same.

Therefore, our objective is to force result to be equal to target and we do that by moving pointers i and j to the right and left, respectively, to increase or decrease result until it is equal to target. We are guaranteed to achieve this goal because the problem states that there will always be exactly one valid solution.

In Python, this solution is implemented as:

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers) - 1
        while l < r:
            result = numbers[l] + numbers[r]
            if result < target:
                l += 1
            elif result > target:
                r -= 1
            else:
                return [l+1, r+1]

Because we iterate over the numbers array once, then only $O(n)$ iterations are required, and we still only need $O(1)$ space since there are no data structures that scale in size as a function of the size of the numbers array.