Trusted answers to developer questions

Muhammad Muzammil

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`

.

There can be two approaches to solve this problem:

- Naive approach
- Efficient 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.

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()

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)$.

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

CONTRIBUTOR

Muhammad Muzammil

RELATED COURSES

View all Courses

Keep Exploring

Related Courses