The Two-Sum problem is a simple interview question where:
- …given an array of integers of varying values (both positive and negative; they may repeat)…
- …and a target integer that is achievable…
- …identify the 2 integers in the array (by index) that - when summed together - equate to the target; an element may only be used once.
I initially thought to try a brute-force solution, wherein I would iterate over every entry in the list and see if that would match to an entry we had seen before:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
tgt = target
found = set()
for idx,num in enumerate(nums):
#Check if a solution was found
if len(found) > 0 and num <= tgt:
for entry in found:
if num == entry[2]:
return [entry[0],idx]
if num <= tgt:
found.add((idx,num,tgt-num))
The above code was wrong:
- First, I thought I had assumed that every target would be a positive integer; I failed to consider that the target (and the elements within the list) could be negative. The above code fails to account for those possibilities
I then tried a second approach:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
tgt = target
lst = sorted(nums)
sidx = 0
lidx = len(lst)-1
small = lst[sidx]
lrg = lst[lidx]
while(small + lrg != tgt):
total = small + lrg
if total > tgt:
lidx -= 1
elif total < tgt:
sidx += 1
small = lst[sidx]
lrg = lst[lidx]
return [sidx,lidx]
This one was a little better, since now it accounts for negative values. I even tried to implement an optimization solution by considering sorting the list first! In this approach, I would sort the list, then use 2 pointers to increment (from the bottom) and decrement (from the top) until the values were found.
While this solution would work in discovering the values, it fails to return the correct index positions; this is because this approach sorts the elements, which changes the elements index position.
I then tried to modify the approach:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
tgt = target
lst = sorted(nums)
sidx = 0
lidx = len(lst)-1
small = lst[sidx]
lrg = lst[lidx]
while(small + lrg != tgt):
total = small + lrg
if total > tgt:
lidx -= 1
elif total < tgt:
sidx += 1
small = lst[sidx]
lrg = lst[lidx]
print(small,lrg)
return [nums.index(small), nums.index(lrg)]
This approach was the same as the last, only now we are returning the index values of the original list. However, this approach also isn’t sufficient, because the index() function returns the first instance of a value in a list. This means that if a solution is reliant on a repeated value (e.g. 3 + 3 = 6), this function will return the index value of the first match it finds (and not the second).
I then thought of changing my approach altogether, this time landing on the appropriate (and - it turns out - optimal) solution:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
tgt = target
dic = {}
for idx,val in enumerate(nums):
match = tgt - (val)
if match in dic.keys():
#return
return [dic[match], idx]
else:
dic[val] = idx
In this final approach, I leverage the O(1) lookup time benefits of the python dictionary data structure to record values seen as we iterate along the list; every time we encounter a value, we’ll look back at our dictionary to see if we’ve ever seen its matching counterpart.
Since we will only go through the list once, the time complexity of the algorithm is O(n). Likewise, the space complexity is also O(n), since the amount of space required is dependent on the size of the array.