Two Sum II, Input Array Is Sorted

Step 1: The simple way

Trying every pair takes O(n²). A hash map gets O(n) time but uses O(n) space, which the problem does not allow. The sorted order is the hint for something better.

Step 2: Start with the smallest and the largest

Put left on the first element and right on the last, and look at their sum.

• Sum too small: numbers[left] is too small even with the largest partner available, so it can never be part of the answer. Move left right.
• Sum too large: numbers[right] is too large even with the smallest partner available. Move right left.
• Sum equal: found it.

Step 3: Why nothing is missed

Each move throws away one element, and only an element that we have shown to be useless. So the answer pair is never skipped, and the pointers meet after at most n steps.

numbers = [2, 3, 4], target = 6.

With target = 7 instead: 2 + 4 = 6 is too small, so left moves to 3, and 3 + 4 = 7 gives [2, 3].

The indices returned are 1-based, as the problem asks.

import java.util.Arrays;

public class TwoSumII {

    public static int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[] {left + 1, right + 1};   // the problem uses 1-based indices
            } else if (sum < target) {
                left++;                       // need a bigger sum
            } else {
                right--;                      // need a smaller sum
            }
        }
        return new int[] {-1, -1};            // not reached: a solution always exists
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(twoSum(new int[] {2, 7, 11, 15}, 9)));   // [1, 2]
        System.out.println(Arrays.toString(twoSum(new int[] {2, 3, 4}, 6)));        // [1, 3]
        System.out.println(Arrays.toString(twoSum(new int[] {-1, 0}, -1)));         // [1, 2]
    }
}

The original implementation, TwoSumII.java, is on GitHub.

• Time: O(n): each step moves one pointer.
• Space: O(1).

For an unsorted array, use a hash map instead, as in Two Sum. Fixing one number and running this search on the rest gives 3Sum. This problem is the example used in Two Pointers Basics to show why each pointer move is safe.