Two Sum II, Input Array Is Sorted

Find the two numbers in a sorted array that add up to a target, with one pointer starting at each end.

Find two numbers in an integer array numbers, sorted from smallest to largest, that sit at two different positions and add up to a number target. Return their positions as [index1, index2], with index1 < index2, counting positions from 1 rather than 0. Every input has exactly one such pair, every number is between -1,000 and 1,000, and the method may use only a fixed amount of extra memory.

Example 1
Input: numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]
Explanation: 2 + 7 = 9, and 2 and 7 sit at positions 1 and 2.
Example 2
Input: numbers = [2, 3, 4], target = 6
Output: [1, 3]
Explanation: 2 + 4 = 6.
Example 3
Input: numbers = [-1, 0], target = -1
Output: [1, 2]
Solution

The Idea

Say you have a gift card worth 9 and a shelf of six items priced 1, 3, 4, 5, 7 and 11, from cheapest to most expensive. You want two items that use up the card exactly. With six items there are 15 ways to pick two, and one of them works: 4 and 5.

You could test all 15 pairs, but that ignores something useful: the prices are in order. So which pair should you look at first, and what does a wrong guess tell you?

Start with the cheapest and the most expensive item: 1 + 11 = 12, which is too much. Now think about the 11. It is already paired with the cheapest item on the shelf, and that is still too much. Any other partner costs more, so the 11 can never be part of the answer. Put it aside and try 1 + 7 = 8. That is too little, and the 1 is paired with the most expensive item left, so no partner can save it. The 1 goes aside too.

Every guess rules out one item for good. Keep one marker, left, on the cheapest item still in play and another, right, on the most expensive. Look at the picture below.

The sorted array 1, 3, 4, 5, 7, 11 with target 9. left starts at 1 and right at 11. 1 + 11 = 12 is too big, so right moves left. 1 + 7 = 8 is too small, so left moves right. 3 + 7 = 10 is too big, 3 + 5 = 8 is too small, and 4 + 5 = 9 is a match at positions 3 and 4.

Each row is one guess, and the grey boxes are the numbers already ruled out. In the first row, 1 + 11 = 12 is too big, so right moves left onto 7. In the second, 1 + 7 = 8 is too small, so left moves right onto 3. Two more moves follow, and in the last row 4 + 5 = 9 is the match, at positions 3 and 4.

So the pair is found by walking two markers toward each other, never testing a pair that could not work. The markers are positions in the array, usually called pointers, and this way of searching is called the two-pointer technique.

Solution Approach

Turning that idea into code means settling three things: which pointer moves after each guess, when the search stops, and how to report the positions.

Moving the pointers

Why not simply try every pair? Two loops, one inside the other, would do it, but an array of n numbers has n(n - 1)/2 pairs. For 30,000 numbers that is about 450 million sums. A hash map, a table that finds a stored value in one step, can find the pair in one pass by remembering each number it has seen. But it stores up to n numbers, and the problem allows only a fixed amount of extra memory.

The two pointers avoid both costs: they make one pass and store only two positions. left starts at the first position and right at the last. When their sum is smaller than target, the number at left is paired with the largest number still in play and still falls short. Every other partner is smaller, so that number belongs to no pair, and left moves right. When the sum is too big, the same reasoning the other way round moves right left.

Each move rules out only a number that cannot be in the answer, so the pair is never skipped.

When the search stops

How long should the pointers keep moving? Until the sum matches, or until left reaches right. The two numbers must come from two different positions, so the pointers may never stand on the same one. Two equal numbers at different positions are fine: in [1, 3, 3, 8] with target 6, the two 3s make the pair.

Reporting the positions

Java arrays count positions from 0, but the answer counts them from 1. So the method returns left + 1 and right + 1. Since left is always to the left of right, the smaller position comes first, as the problem asks.

Java Solution

The method twoSum works in these steps:

  1. First, put left on position 0 and right on the last position, numbers.length - 1.
  2. Loop with while (left < right), so the two pointers always mark two different positions.
  3. Inside the loop, add the two numbers into sum. With every number between -1,000 and 1,000, the sum fits easily in an int. If sum equals target, return left + 1 and right + 1.
  4. If sum is too small, move left one place right. If it is too big, move right one place left.
  5. If the pointers meet without a match, return [-1, -1]. A valid input always has a pair, so this line only runs for an input that breaks that promise.

The main method runs the three examples, the six numbers from the picture, an array with the same value twice, and an array where no pair adds up to the target.

Java
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};   // positions count from 1
            } else if (sum < target) {
                left++;                       // too small: take a bigger left value
            } else {
                right--;                      // too big: take a smaller right value
            }
        }
        return new int[] {-1, -1};            // no pair adds up to target
    }

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

Running it prints:

Output
[1, 2]
[1, 3]
[1, 2]
[3, 4]
[2, 3]
[-1, -1]

The answers [1, 2], [1, 3] and [1, 2] match the three examples. Look at the fourth line, [3, 4]: those are the positions of 4 and 5, reached after the four moves in the picture.

The fifth line, [2, 3], comes from [1, 3, 3, 8] with target 6. The two 3s sit at positions 2 and 3, so together they count as a pair.

The last line, [-1, -1], comes from [1, 3, 4] with target 6, where no two different positions add up to 6. Here the loop condition matters. With left <= right instead, both pointers reach the 3 at position 2, and 3 + 3 = 6 counts as a match. That version returns [2, 2], using the same 3 twice.

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

Complexity

The work is one walk of the two pointers toward each other, with one sum per step.

  • Time: O(n) for n numbers. The pointers start n - 1 places apart, and every pass of the loop moves one of them one place closer, so the loop runs at most n - 1 times.
  • Space: O(1). The method keeps only left, right and sum, plus the two-number answer, however long the array is. That meets the problem's rule of a fixed amount of extra memory.

When the array is not sorted, a hash map is the way to go: see Two Sum.