Classic two sum problem

Problem

Given the array of integer, A = {1, 6, 8, 2. 7}, and target sum, 9, you need to write the problem to tell where there are two integers whose sum equals 9.

2022-03-22: Additional constraints

How will you change your algorithm if the input has duplicate values and you can't use the same values twice? You should return all matching number pairs.

A = {1,3,3,5,7,8,4,4}, target sum 8

[ [3,5], [4,4]]

This is a classic two-sum problem.

Given the array, A, and a target sum, S.
Basically, we can use HashTable, which provides $O(1)$ for accessing the element with a key, to search the value, L, where $$L = S - A_{i} \text {, where}  A_{i} \in A$$ .

For each $A_{i} \in A$, we can perform the check stated above. This takes $O(N)$ time thanks to the HashTable.

Here is the rough algorithm:

1. Add all numbers in A to the hash table.

2. Check if L exists in the hash table. Return true if exists.

Here is the algorithm running in $O(N)$, theoretically but $O( N \log N) practically due to the std::set data structure.

	#include <set>
	#include <iostream>
	using namespace std;
	bool find_sum(int *input, int n, int sum)
	{
	set<int> hashtable;
	for (int i = 0; i < n; i++)
	{
	hashtable.insert(input[i]);
	}
	for (int i = 0; i < n; i++)
	{
	if (hashtable.find(sum - input[i]) != hashtable.end())
	return true;
	}
	return false;
	}
	int main ()
	{
	int input[5] = {1, 6, 8, 2, 7};
	cout <<" sum = 9 found = "<<find_sum(input, 5, 9) <<endl;
	return 1;
	}

view raw two_sum.cpp hosted with ❤ by GitHub

Practice statistics

10 mins: to write up the code.


UPDATE: 2019-09-24

Encounter this problem during the interview and could think of the solution with HashTable. I came up with a different solution using Dynamic problems. However, it was overkill.

Here is the solution in Python running in $O(N)$.

First one is brute force example running in $O(N!)$ and Second one runs faster in $O(N)$.

	# solution with O(N!)
	def twoSum(L, target):
	for i in range(len(L)):
	for j in range(i+1, len(L), 1):
	if L[i] + L[j] == target:
	return [L[i], L[j]]
	return []
	# solutin with O(N)
	def twoSumHash(L, target):
	hash = {i:i for i in L}
	for i in L:
	left = target - i
	if left in hash:
	return [i, left]
	return []
	a = [1,4,5,2,8,3,6,9]
	target = 6
	print("input = {}, target ={}, answer = {}".format(a, target, twoSum(a, target)))
	print("input = {}, target ={}, answer with Hash = {}".format(a, target, twoSumHash(a, target)))

view raw two_sum_with_hash.py hosted with ❤ by GitHub

UPDATE: 2022-03-27

Encounter the new two-sum variation and got it wrong during the interview. It wasn't that important interview but I felt bad.

If there are duplicate numbers in the input and we can't use the same number twice in the answer, we need to keep the count of the numbers in the hashmap and keep track of the count for both numbers used in the answer. 

The initial answer did not decrease the count for the first number and got the wrong answer.

Here is the python answer running in $O(N)$ time.

	def two_sum(numbers, target):
	number_map = {}
	# build the hash map with a number as key and the number of occurrence as value.
	for i in range(len(numbers)):
	number = numbers[i]
	if number in number_map:
	number_map[number] = number_map[number] + 1
	else:
	number_map[number] = 1
	# iterate over numbers and find the all matching pairs
	output = []
	for i in range(len(numbers)):
	number = numbers[i]
	residue = target - number
	if number_map[number] > 0 and residue in number_map and number_map[residue] > 0:
	output.append([number, residue])
	number_map[residue] = number_map[residue] - 1
	number_map[number] = number_map[number] - 1
	return output
	input = [1,3,3,5,7,8,4,4, 2, 6, 2]
	target = 8
	output = two_sum(input, target)
	print(output)

view raw two_sum_duplicate.py hosted with ❤ by GitHub