Solution: Two Pointers

Let’s start with an observation. Suppose numbers = [2, 7, 11, 15] and the target is 9. 15 is larger than the target, so it cannot be part of a valid pair. The same reasoning rules out 11. That leaves 2 and 7, which do add up to the target.

Now suppose numbers = [2, 7, 11, 15] and the target is 18. The largest value is 15, which is smaller than the target, so it could be part of a valid pair. However, if you add 15 to the smallest value, 2, the sum is 17, which is still smaller than the target. So 2 cannot be part of a valid pair because even when paired with the largest value it is too small. Now if you move to the next smallest value, 7, and add it to 15, the sum is 22, which is larger than the target. So 15 cannot be part of a valid pair because even when paired with the smallest remaining value it is too large. That leaves 7 and 11, which do add up to the target.

So we can rule out the largest values in the array, and we can also rule out the smallest values. If the sum of the smallest and largest is too big, the largest is too big. If the sum is too small, the smallest is too small.

Let’s use that. Start at the two ends of the array. The leftmost value is the smallest and the rightmost is the largest, because the array is sorted. Add those two and compare the sum with the target. One of three things happens, and in two of them we can rule out a value for good:

  • If the sum is too big, the largest value is already too big even when paired with the smallest remaining value. Paired with anything else the sum would only be larger, so the largest value is not in any valid pair, and we can drop it for good.
  • If the sum is too small, the same reasoning rules out the smallest value: even paired with the largest remaining value the sum is too small, so it is not in any pair, and we drop it.
  • If the sum equals the target, we are done.

Here is the code:

public static int[] twoSum(int[] numbers, int target) {
  int left = 0;                    // Start from beginning
  int right = numbers.length - 1;  // Start from end

  while (left < right) {
    int sum = numbers[left] + numbers[right];

    if (sum == target) {
      return new int[]{left, right};  // Found it!
    } else if (sum < target) {
      // Sum too small, need larger number
      left++;
    } else {
      // Sum too large, need smaller number
      right--;
    }
  }

  return new int[0];  // We never reach here because the problem guarantees a solution exists
}

The problem guarantees a solution exists, so the two pointers are sure to find it.

Let’s trace this on numbers = [2, 7, 11, 15] with target = 9. We start with left at the beginning and right at the end:

┌────┬────┬────┬────┐
│  2 │  7 │ 11 │ 15 │
└────┴────┴────┴────┘
   ↑              ↑
 left           right

The sum is 2 + 15 = 17, which is greater than 9. The sum is too big, so we move right inward to shrink it:

┌────┬────┬────┬────┐
│  2 │  7 │ 11 │░15░│
└────┴────┴────┴────┘
   ↑         ↑
 left      right

Now the sum is 2 + 11 = 13, still greater than 9. Too big again, so we move right inward once more:

┌────┬────┬────┬────┐
│  2 │  7 │░11░│░15░│
└────┴────┴────┴────┘
   ↑    ↑
 left right

This time the sum is 2 + 7 = 9, which equals the target. We found the pair and return [0, 1]. Notice that the shaded cells fall outside the [left, right] window. Every time we move a pointer inward, we rule out a cell for good, so the window only gets smaller.

What does this cost? Every pass through the loop either returns or moves one of the two pointers inward by one. The pointers start apart and the loop stops when they meet, so there are at most passes. The body is an addition and a comparison, which is constant work. Constant work done at most times is .

The solution here is another example of the two-pointer technique. We saw an earlier example of this technique used to remove duplicates from a sorted array. The two-pointer technique is a common pattern for solving problems on sorted arrays, and it often gives an solution.