Leetcode 167: Two Sum II — Input Array is Sorted

In this exercise, we need to find the unique pair of indices [x, y] such that numbers[x] + numbers[y] == target, with numbers a sorted array.

a. A little bit of Math

We need to use the sorted array in order not to check every single pair. How do we eliminate pairs?

If numbers[i] + numbers[j] < target with i < j, then numbers[i] + numbers[k] < target for all k ≤ j, and so all these pairs don’t need to be checked. We have a similar result with numbers[i] + numbers[j] >target.

So if numbers[0] + numbers[n-1] < target with n the array length, then all pairs (0, j) are such that numbers[0] + numbers[j] < target, and numbers[0] isn’t part of the solution. We use this property to eliminate one element of numbers at every step.

b. Algorithm

We use 2-pointers x and y starting at both ends of the array. If the sum numbers[x] + numbers[y] < target, we increment x. If the sum numbers[x] + numbers[y] >target, we decrement y. Of course if the sum is equal to target, then we return.

public int[] twoSum(int[] numbers, int target) {
    int x = 0;
    int y = numbers.length - 1;
    while(x < y) {
        if (numbers[x] + numbers[y] == target) {
            return new int[]{x+1, y+1};
        }
        if (numbers[x] + numbers[y] < target) {
            x++;
        } else {
            y--;
        }
    }
    return new int[0];
}

c. Space and time complexity

The algorithm is O(n) in time because of the while loop, and O(1) in space.