Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

two
sum
problem
python
hashtable

How to implement the two sum problem in Python

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][3, 5, 2, -4, 8, 11] and the value of S is 77, then the program should return pairs (11,4)(11,-4) and (2,5)(2,5) since 11+(4)11 +(-4) and 2+52+5 are equal to 77.

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(n2)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)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
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring