Interview Questions

Two sum problem

The two sum problem is a common interview question, and it is a variation of the subset sum problem. There is a popular dynamic programming solution for the subset sum problem, but for the two sum problem we can actually write an algorithm that runs in O(*n*) time. The challenge is to find all the pairs of two integers in an unsorted array that sum up to a given S.
## Naive solution

A naive approach to this problem would be to loop through each number and then loop again through the array looking for a pair that sums to S. The running time for the below solution would be O(*n*^{2}) because in the worst case we are looping through the array twice to find a pair.
## Faster solution

We can write a faster algorithm that will find pairs that sum to S in linear time. The algorithm below makes use of hash tables which have a constant lookup time. As we pass through each element in the array, we check to see if S minus the current element exists in the hash table. We only need to loop through the array once, resulting in a running time of O(*n*) since each lookup and insertion in a hash table is O(1).
## Example

If the array is: [4, 5, 1, 8] and the sum is 6 the algorithm would proceed with the steps below:
## Code for faster solution

## Sources

http://www.careercup.com/question?id=15206700
http://www.glassdoor.com/Interview/Given-a-sorted-array-write-a-program-to-decide-if-two-elements-sum-up-to-a-third-QTN_242990.htm
http://www.glassdoor.com/Interview/Given-a-sum-find-two-numbers-in-an-array-with-that-sum-QTN_864790.htm

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.

// our two sum function which will return // all pairs in the array that sum up to S function twoSum(arr, S) { var sums = []; // check each element in array for (var i = 0; i < arr.length; i++) { // check each other element in the array for (var j = i + 1; j < arr.length; j++) { // determine if these two elements sum to S if (arr[i] + arr[j] === S) { sums.push([arr[i], arr[j]]); } } } // return all pairs of integers that sum to S return sums; } twoSum([3, 5, 2, -4, 8, 11], 7);

# our two sum function which will return # all pairs in the list that sum up to S def twoSum(arr, S): sums = [] # check each element in array for i in range(0, len(arr)): # check each other element in the array for j in range(i+1, len(arr)): # determine if these two elements sum to S if (arr[i] + arr[j] == S): sums.append([arr[i], arr[j]]) # return all pairs of integers that sum to S return sums print twoSum([3, 5, 2, -4, 8, 11], 7)

(1) The hash table is initially empty and the first element in the array is 4. We simply put 4 into the hash table.
(2) The next element is 5. We check to see if the sum minus the current element exists in the hash table. 6 - 5 = 1 does not exist in the hash table. So add 5 to the hash table.
(3) The next element is 1. We check to see if the sum minus the current element exists in the hash table. 6 - 1 = 5 does exist in the hash table so we found a pair!

// our two sum function which will return // all pairs in the array that sum up to S function twoSum(arr, S) { var sums = []; var hashTable = {}; // check each element in array for (var i = 0; i < arr.length; i++) { // calculate S - current element var sumMinusElement = S - arr[i]; // check if this number exists in hash table // if so then we found a pair of numbers that sum to S if (hashTable[sumMinusElement.toString()] !== undefined) { sums.push([arr[i], sumMinusElement]); } // add the current number to the hash table hashTable[arr[i].toString()] = arr[i]; } // return all pairs of integers that sum to S return sums; } twoSum([3, 5, 2, -4, 8, 11], 7);

# our two sum function which will return # all pairs in the list that sum up to S def twoSum(arr, S): sums = [] hashTable = {} # check each element in array for i in range(0, len(arr)): # calculate S minus current element sumMinusElement = S - arr[i] # check if this number exists in hash table # if so then we found a pair of numbers that sum to S if sumMinusElement in hashTable: sums.append([arr[i], sumMinusElement]) # add the current number to the hash table hashTable[arr[i]] = arr[i] # return all pairs of integers that sum to S return sums print twoSum([3, 5, 2, -4, 8, 11], 7)

mrdaniel
published this on 11/9/15 **|**

17

why do you have to convert, .toString()?

df5890

commented on 04/08/16

5

@df5890, in JavaScript hash tables, the keys cannot be integers. JavaScript will automatically convert the number to a string, but I just did it explicitly in the code above.
http://stackoverflow.com/questions/2002923/javascript-using-integer-as-key-in-associative-array

mrdaniel

commented on 04/13/16

3

what if there are duplicates in the given array?

jayceeyili

commented on 09/27/16

2

This solution would be better using a set over a hashTable.

dylanshine

commented on 08/27/18

1

How do i get the brackets to show up in my browser, when I run the code it shows up like this 5,2,-4,11, instead of
[[5,2],[-4,11]]

jcapra

commented on 10/13/16

1

Can you guys give code/comments for the ArrayAdditionI version of this classic problem, ie. returns true if there is a subset of any number of elements (not just two) adding up to the largest element? The solutions provided don't have comments for the most part. Thanks.

rhodesd

commented on 01/24/16

0

Further to my previous comment, to make the function report the results in the order specified (in order that the first number of pair appears in array), you need to include some way to sort the resulting array. Not sure whether this is more efficient that a nested loop to begin with.

function TwoSum(arr) { var S = arr.shift(); var sums = []; var hashTable = {}; // check each element in array for (var i = 0; i < arr.length; i++) { // add the current number to the hash table; using the array index as the value hashTable[arr[i].toString()] = i; // calculate S - current element var sumMinusElement = S - arr[i]; // check if this number exists in hash table // if so then we found a pair of numbers that sum to S //push object containing array (the pair) and the original index into sums array if (hashTable[sumMinusElement] !== undefined) { sums.push({pair: [sumMinusElement, arr[i]], origIndex: hashTable[sumMinusElement]}); } } //Sort sums array by origIndex sums.sort((a,b) => a.origIndex - b.origIndex); // create results string by joining the pair arrays let string = sums.map(element => element.pair).join(' '); return string; } TwoSum(readline());

ugotabkdin

commented on 12/07/18

0

The solution provided in explanation above efficiently finds all the pairs, but it DOES NOT correctly solve the challenge because it cannot order the results "in the order the first number appears in the array" (as specified in challenge).
I have wrestled with this and don't see a way to report results as specified without another loop over the array. I.e., I don't think there is a more efficient approach than a nested loop to check each array element against each subsequent element.
Does anyone else?

ugotabkdin

commented on 12/07/18

0

This will handle the duplicates too

package main import "fmt" func twoSum(nums []int, target int) [][]int { var r [][]int = make([][]int, 0) var m map[int]int = make(map[int]int, 0) for p, i:= range nums { j := target - i if pos, ok := m[j]; ok { if pos != p { r = append(r, []int{j, i}) } } else { m[i] = p } } return r } func main() { fmt.Println(twoSum([]int{1,4,2,3,6,5,0,3}, 6)) }

rayqiu

commented on 11/12/18

-7

This actually doesn't even correctly solve the challenge. It returns an empty array

adrian08

commented on 04/07/17

Log in to submit a comment.