Trusted answers to developer questions

Educative Answers Team

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$.

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.

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:

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

Copyright Â©2022 Educative, Inc. All rights reserved

RELATED COURSES

View all Courses

Keep Exploring

Related Courses