Two Sum – Problem Statement
We have an array of integers called nums and a target value. We need to return the indices of two numbers, say x and y that add up to target.
Assumptions
- Each given input will have exactly one solution
- Same element cannot be used twice
- Order of indices does not matter
Examples
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1] where x = 2 and y = 7
Input: nums = [4, 4], target = 8
Output: [0, 1] where x = 4 and y = 4
Thought process
What’s the brute force way to check if two numbers add up to a target value in an array?
For each value nums[i] where i = 0 initially, we traverse the list from nums[i+1] and see which two indices add up to a target value. The complexity of this will be O(n2) since we loop through the remaining n-i elements for each i. So the first optimization here would be to try and see if we can reduce the traversal to just once.
For a value x, to check if there is another value y = target – x present in the array, we need a way to do a fast lookup without going through the whole array. A dictionary is the data structure that comes to mind in that case. How to design this data structure? What will our keys and values be?
To search for a value y = target – x, we have to store the values in nums as the keys in dictionary to search for. The value for each key can then be its index in the nums array so that we can directly return the indices as our result.
Complexity
O(N) time to traverse the array once, O(1) to look up values.
O(N) space for the look up dictionary
Solution
def two_sum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
look_up = {}
for i, x in enumerate(nums):
y = target - x
# Additional condition to make sure we don't return the same index twice
if y in look_up and look_up[y] != i:
return [i, look_up[y]]
look_up[x] = i
return []
Two Sum with Sorted Array – Problem Statement
This is a slight variation of the problem above where the input array nums is sorted in ascending order and we need to find two numbers that add up to a target value.
Assumptions
- Each input will have exactly one solution
- Same element cannot be used twice to add up to a target
Examples
Input: nums[2, 7, 11, 15], target = 9
Output: [0, 1]
Thought Process
Again, the brute force way of solving this problem would be to traverse the array using two for loops to find two numbers that add up to a target. This way we are not using the added benefit that the array is sorted in ascending order.
This means we can apply the two pointer technique here. This works great in many scenarios especially when the input array is sorted. We can use two pointers starting at two ends of the array. If the numbers they are pointing to do not add up to our target value, there are two decisions that can be made from then on. If the sum is greater than target, this means we have to move the end pointer to the left, otherwise move the start pointer to the right. See below.
Complexity
O(N) time since we traverse the array at most once in case the two elements are at the center of the array.
O(1) space since no additional space is used except for a couple of variables.
Solution
def two_sum(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
s = 0
e = len(nums) - 1
while s < e:
if nums[s] + nums[e] == target:
return [s, e]
elif nums[s] + nums[e] < target:
s += 1
else:
e -= 1
return []
Two Sum with Sorted Array and Duplicates
Let’s consider the exact same problem as above but now our result can have multiple solutions that add up to the same target value but it cannot contain duplicates.
Instead of returning the indices, let’s return the numbers to make it easier for understanding.
Assumptions
- Each input will have multiple solutions
- Same element cannot be used twice to add up to a target
- The solution cannot contain duplicate sets
Examples
Input: nums = [2, 2, 4, 4, 5, 7, 7, 9, 11, 15], target = 9
Output: [[2, 7], [4, 5]]
Thought Process
In order to return multiple solutions, once we find nums[s] + nums[e] = target, we have to advance our start s pointer and continue to look for other solutions. We can collect the solutions inside a result list. If we don’t account for duplicate solutions, this is how our code will look. For the given input above, this code will return all solutions including the duplicates [[2, 7], [2, 7], [4, 5], [4, 5]].
def two_sum(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
s = 0
e = len(nums) - 1
result = []
while s < e:
if nums[s] + nums[e] == target:
result.append([nums[s], nums[e]])
s += 1 # Advance the starting pointer to continue to look for other solutions
elif nums[s] + nums[e] < target:
s += 1
else:
e -= 1
return result
In order to avoid duplicate solutions since our array is already sorted, we can compare the current value with the previous value. If they are the same, we are about to build the exact same solution that was found in the previous run, so we can skip it. For example, in [2, 2, 4, 4, 5, 7, 7, 9, 11, 15], when i = 1, nums[i] = 2 = nums[i-1] = 2, which will again yield [2, 7] as a duplicate solution, so let’s skip it and advance the starting s pointer. Then our solution can be slightly modified as shown below.
Complexity
O(N) time
O(1) space since we don’t usually include result as additional space
Solution
def two_sum(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
s = 0
e = len(nums) - 1
result = []
while s < e:
if nums[s] + nums[e] == target:
result.append([nums[s], nums[e]])
s += 1 # Advance the starting pointer to continue to look for other solutions
# Skip duplicate solutions
while s < e and nums[s] == nums[s-1]:
s += 1
elif nums[s] + nums[e] < target:
s += 1
else:
e -= 1
return result
That Girl Coder 