Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

algorithm
python
communitycreator

How to solve the two-sum problem

Muhammad Muzammil

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 ee^{'} equals the target.

However, this will result in the time complexity of O(n2)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)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])
		sums.add(val)
	return res

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

RELATED TAGS

algorithm
python
communitycreator
RELATED COURSES

View all Courses

Keep Exploring