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 and the value of S is , then the program should return pairs and since and are equal to .
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 arrayfor i in range(len(num_arr) - 1):# search other element in the arrayfor j in range(i + 1, len(num_arr)):# if these two elemets sum to pair_sum, print the pairif num_arr[i] + num_arr[j] == pair_sum:print("Pair with sum", pair_sum,"is: (", num_arr[i],",",num_arr[j],")")# Driver Codenum_arr = [3, 5, 2, -4, 8, 11]pair_sum = 7# Function call inside printtwoSumNaive(num_arr, pair_sum)
This may be the intuitive approach, however, the running time complexity for the solution will be 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 () 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:
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 Codenum_arr = [4, 5, 1, 8]pair_sum = 9# Calling functiontwoSumHashing(num_arr, pair_sum)
RELATED TAGS
