Solution of Two Sum Problem in Python

In this post, we will give you solution of two sum problem in python with detailed exaplanation and example.

The Two Sum problem is a basic LeetCode problem generally asked in coding interviews and programming competitions. Let’s first understand what the Two Sum problem is and then jump to its solution.

What is Two Sum Problem?

The two-sum problem involves finding two numbers in an array that add up to a specific target sum.

For example, given an array of numbers ([8, 7, 5, 4, 2]) and a target number (for example, 7), you need to return a pair of numbers that sum up to the target (in this case, [5, 2])

Different Ways To Solve Two Sum Problem

There are generally two common ways to solve the two sum problem in Python.

1. Using a brute-force approach
2. Using hash map technique

Let’s see both methods one by one with the help of an example.

Using a brute-force approach

The brute-force approach is the simplest and easiest approach to solve the two sum problem. We simply go through each element of the array with a nested loop, adding them together to see if they equal the target value. If they do, we print them.

Let’s see it practically, but before writing a code you must have familiar with some python programming concepts:

1. Python for-loop &
2. Python list

Source Code

arr = [8, 7, 5, 4, 2]
target = 7

for i in range(len(arr)):
    for j in range(i+1, len(arr)):
        if (arr[i] + arr[j]) == target:
            print([arr[i], arr[j]])

Output

[5, 2]

The time complexity of the brute-force approach is O(n²), which is why people prefer using the hash map technique, as its time complexity is lower compared to the brute-force method.

Using Hash Map Technique

In the hash map technique, we create a hash table using a Python dictionary, where elements are stored as keys and their indices as values. Initially, this hash table is empty.

We iterate through the array using enumerate() function, calculating each element’s complement (the value needed to reach the target sum). If the complement exists in the hash table, we return the pair. Otherwise, we add the element to the hash table. This process continues until we find a solution or iterate through the entire array.

Let’s see it practically.

Source Code

arr = [1,2,3,4,5,6,7]
target = 7

hash_table = {}

for i, num in enumerate(arr):
    complement = target - num
    if complement in hash_table:
        print([complement, arr[i]])
    hash_table[num] = i

Output

[3, 4]
[2, 5]
[1, 6]

The time complexity of the hash map method is O(n) and that’s why it is more efficient than the brute-force method.

NOTE: I’ve seen many programs where people return indices of numbers whose sum is equal to the target, but here, we return the numbers directly for a clearer output.

This concludes our discussion on the two sum problem. I hope this post helps you to solve it. Thank you for reading, and see you in the next article!