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][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)

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved