Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

(Java Code on Github at the bottom of the post. )

Q: What is the unknown?
A: the indices of the two numbers in the array that add up to a target value.
Q: What are the data?
A: An array of integers and a target value.
Q: What are the constraints? Ambiguities?
A: The index is not zero-based. The example gives us a sorted array but it may not be sorted in other cases. There may be duplicates in the array.
Q: Have you seen this problem before?
A: Yes, but I want to redo this problem like a clean slate rather than memorize the solution to it.
Q: How do we approach it?
A: One possible solution would be for each element in the array, subtract it from the target value and check if the remained value is also in the array. But that would take O(n^2) time (and O(1) space).
Q: So can we do better? If we can, what is the bottleneck?
A: The bottleneck is that we have to scan through the whole array to see if a value exist. If we can speed up this lookup process, it would help to speed up the whole algorithm. Current lookup is O(n) and possible upgrades are O(logn) and O(1). Now what algorithm or data structure can achieve O(logn) and O(1) lookup? I would say BST and Hashtable. Since both data structure uses O(n) space, we will consider hashtable since it is faster in lookup.
Q: OK, so how does hashtable lookup fit in here?
A: Well, I think we need to scan through the array first and count the frequency of each value. Then in the second pass, we calculate the remained value by subtract the current value from the target and check if the remained value exists in the hashtable. If not, we move on to the next one. If yes, then we have found one (here be careful about duplicates and values like 4-2=2).
Q: Yes, we can do that, but the problem asks for the index of the two numbers, not the numbers themselves.
A: Ah yes, we can use another hashtable to keep track of the indices of each value or we can scan through the array to find the index of these two values. The first way require extra O(n) space while the second way requires an extra pass of O(n) time.

Q: OK, one question: is it possible that an number overflow happens in your algorithm? If yes, how do you solve it?
A: Suppose that our target value is Integer.MIN_VALUE + 1 and our array is [3, -1, Integer.MIN_VALUE + 2]. In this case, if we subtract 3 from our target value, we will get out of Integer range. Similarly, if our target value is Integer.MAX_VALUE – 3 and our array is [-4, 1, Integer.MAX_VALUE – 4], we will get the same type of problem when we subtract -4 from our target value. So it looks like that we need to validate the range before subtracting.
Q: Yes, you got this part right. Now do you have any idea of how to do it?
A: Well, the target value is in range. Basically we need to check if we subtract the current value from the target, would it be outside of [Integer.MIN_VALUE, Integer.MAX_VALUE]? To get lower than Integer.MIN_VALUE, we need to subtract a positive number from the target. To get higher than Integer.MAX_VALUE, we need to subtract a negative number from the target. So if the current value is positive, we check if the MIN plus current is larger than the target. If yes, then it’s going to be out of bound if we do the subtraction. Similarly, if the current value is negative, we check if the MAX plus the current value is smaller than the target. If yes, then it’s going to be out of bound if we do the subtraction. Two examples here:
Say the range is [-10, 10]. target value is 3, current value is -8. 10-8 = 2 is smaller than 3, so this is going to be out of bound.
if the current value is 9, -10 + 9 = -1 is smaller than 3, so subtracting 9 from 3 is OK. We can even drop a graph to illustrate this idea.

Q: GOOD, you got it. Make sure you implement the code. Any other way to solve this problem?
A: Well, yeah we could sort the numbers first but that messes up the index and we have to keep track of the previous index somehow. So that’s not worth it in this problem. If we are only looking at the numbers, this approach may save us some spaces.

Code on github:

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s