The algorithm is necessary for a coding interview for a data scientist and a software engineering job. This article’s topic is one of the most important subjects.
Problem
Write a function to return True if there exists a pair of numbers whose summation equals the given target number, or to return False otherwise. You may assume that an element in a list is an integer.
Solution – Normal Approach
This solution is a simple approach, but not a computationally efficient method. Time Complexity is $O(N^2)$.
The method examines all the sums of two list elements in sequence to determine if they contain the desired result.
def two_sum(nums, target):
"""
Time Complexity O(N^2)
Args:
nums(list): a list of an integer number
target(int): target-integer number
"""
for i in range(len(nums)):
for j in range(len(nums)):
if i != j and target == nums[i] + nums[j]:
return True
return False
Test examples
assert two_sum([10, 2, 3, 1], 5) == True
assert two_sum([1, 2, 3, 4], 1) == False
Solution – Better Approach
This solution is an improved approach, then the Time Complexity is $O(N)$!
The key concept is as follows. First, we choose one element in each iteration. As a result, we can determine the desired element from the “target number – one element”. Second, we check whether the desired element exists in a cache, where the cache is a list containing elements examined in iterations already performed.
By repeating the above procedures, it is possible to determine whether a desired pair of elements is included in the list.
def two_sum(nums, target):
"""
Time Complexity O(N)
Args:
nums(list): a list of an integer number
target(int): target-integer number
"""
cache = set()
for n in nums:
ans = target - n
if ans in cache:
return True
else:
cache.add(n)
return False
Test examples
assert two_sum([10, 2, 3, 1], 5) == True
assert two_sum([1, 2, 3, 4], 1) == False
Appendix: The case that the indices of numbers are required
Problem
Write a function to return the indices of the two numbers whose summation equals the given target number, or to return False otherwise. You may assume that an element in a list is an integer.
Solution
In this case, we should use a hash map, i.e., the dictionary in Python. The concept of a solution is the same as above. However, we have to store the indices of each number.
def two_sum(nums, target):
cache = {}
for i, n in enumerate(nums):
ans = target - n
if ans in cache:
return (cache[i], i)
else:
cache[n] = i
return False
Test examples
assert two_sum([10, 2, 3, 1], 5) == (1, 2)
assert two_sum([1, 2, 3, 4], 1) == False