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 numberstarget[index1, index2]index1 < index2
Example 1
Output: [1, 2]
Explanation: 2 + 7 = 9, and 2 and 7 sit at positions 1 and 2.
Example 2
Output: [1, 3]
Explanation: 2 + 4 = 6.
Example 3
Output: [1, 2]
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, leftright
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 rightleft
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. leftrighttargetleftleftright
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 leftright[1, 3, 3, 8]
Reporting the positions
Java arrays count positions from 0, but the answer counts them from 1. So the method returns left + 1right + 1leftright
Java Solution
The method twoSum
- First, put
on position 0 andleft on the last position,right .numbers.length - 1 - Loop with
, so the two pointers always mark two different positions.while (left < right) - Inside the loop, add the two numbers into
. With every number between -1,000 and 1,000, the sum fits easily in ansum . Ifint equalssum , returntarget andleft + 1 .right + 1 - If
is too small, movesum one place right. If it is too big, moveleft one place left.right - If the pointers meet without a match, return
. A valid input always has a pair, so this line only runs for an input that breaks that promise.[-1, -1]
The main
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:
[1, 2]
[1, 3]
[1, 2]
[3, 4]
[2, 3]
[-1, -1]
The answers [1, 2][1, 3][1, 2][3, 4]
The fifth line, [2, 3][1, 3, 3, 8]
The last line, [-1, -1][1, 3, 4]left <= right[2, 2]
The original implementation,
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 andright , plus the two-number answer, however long the array is. That meets the problem's rule of a fixed amount of extra memory.sum
When the array is not sorted, a hash map is the way to go: see