Related Tags

two
sum
problem
python
hashtable

How to implement the two sum problem in Python

The two sum problem is stated as follows: given an unsorted list and a number S, find all the pairs of numbers in that list such that their sum equals S.

For example, if the list is $[3, 5, 2, -4, 8, 11]$ and the value of S is $7$, then the program should return pairs $(11,-4)$ and $(2,5)$ since $11 +(-4)$ and $2+5$ are equal to $7$.

Naive Solution

The naive solution would be to loop twice through the list to find two numbers that add up to the â€‹provided sum. This is shown below:

def twoSumNaive(num_arr, pair_sum):
# search first element in the array
for i in range(len(num_arr) - 1):
# search other element in the array
for j in range(i + 1, len(num_arr)):
# if these two elemets sum to pair_sum, print the pair
if num_arr[i] + num_arr[j] == pair_sum:
print("Pair with sum", pair_sum,"is: (", num_arr[i],",",num_arr[j],")")

# Driver Code
num_arr = [3, 5, 2, -4, 8, 11]
pair_sum = 7

# Function call inside print
twoSumNaive(num_arr, pair_sum) 

This may be the intuitive approach, however, the running time complexity for the solution will be $O(n^2)$ since we are traversing the list through a nested loop.

Optimal Solution

The two-sum problem can be solved in linear time as well. To accomplish this, we must utilize hash-tables, which have constant ($O(1)$) lookup time.

The algorithm is as follows:

• Initialize an empty hash table.
• For each element in the array:
• Calculate the complement by subtracting the current list element from the given number.
• Look up the complement in the hash table. If it exists, a pair that sums up to the given number has been found.
• Insert the current element of the array into the hash table after you perform the step above.

A pictorial representation of the algorithm is shown below:

1 of 11

Code

def twoSumHashing(num_arr, pair_sum):
sums = []
hashTable = {}

for i in range(len(num_arr)):
complement = pair_sum - num_arr[i]
if complement in hashTable:
print("Pair with sum", pair_sum,"is: (", num_arr[i],",",complement,")")
hashTable[num_arr[i]] = num_arr[i]

# Driver Code
num_arr = [4, 5, 1, 8]
pair_sum = 9

# Calling function
twoSumHashing(num_arr, pair_sum)

RELATED TAGS

two
sum
problem
python
hashtable