Related Tags

algorithm
python
communitycreator

# How to solve the two-sum problem

### Problem statement

Find all the pairs of numbers in an unsorted array arr that sum to a given number target.

For example, if the array is [3, 5, 2, -4, 8, 11] and the sum is 7, your program should return [[11, -4], [2, 5]] because 11 + -4 = 7 and 2 + 5 = 7.

### Solution statement

There can be two approaches to solve this problem:

1. Naive approach
2. Efficient approach

#### 1. Naive approach

The Naive approach would be to choose an element (e) from arr and loop through the rest of it to see if the sum of (e) and some other element $e^{'}$ equals the target.

However, this will result in the time complexity of $O(n^{2})$, which is inefficient.

### Code

#### Example 1

The Python program below implements the algorithm using the Naive approach:

def twoSum (arr, target):
res = []
for i in range(len(arr)):
for j in range(i, len(arr)):
if arr[i] + arr[j] == target:
res.append([arr[i], arr[j]])
return res

def main ():
arr = [3, 5, 2, -4, 8, 11]
target = 7
print(twoSum(arr, target))
main()

#### 2. Efficient approach

We can efficiently solve this problem using sets. We can add every element of arr if the target - arr[i] value exists in the sums set.

This implies that target = arr[i] + (the value in sums), which this will be a solution. This algorithm will run in $O(n)$.

#### Example 2

def twoSum (arr, target):
res = []
sums = set()

for val in arr:
if target - val in sums:
res.append([val, target - val])
return res

def main ():
arr = [3, 5, 2, -4, 8, 11]
target = 7
print(twoSum(arr, target))
main()

RELATED TAGS

algorithm
python
communitycreator

CONTRIBUTOR 