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. 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.
## 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.

You need to be a premium member to see the rest of this question and code.

With our large collection of challengs, tutorials, and solutions, we make it easy for you to become a better coder, prepare for interviews, and learn new skills from more experienced coders.

- 200+ Coding Challenges
- Mock Interview Questions
- 500,000+ Code Solutions
- Algorithm Tutorials
- Interview Prep Courses

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

12

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

df5890

commented on 04/08/16

2

@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

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

0

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

adrian08

commented on 04/07/17

0

To display code include the following tags:

code goes herewhat if there are duplicates in the given array?

jayceeyili

commented on 09/27/16

0

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

Login to submit a comment