# Breaking Down DSAs: Two Sum

### Claire Muller ・2 min read

Another week, another blog post! I really enjoyed writing my last post about solving a popular coding problem, valid anagram, and I thought I would try another this week. So today I'll be walking through my various solutions to the popular two sum problem, using JavaScript.

There are a few different variations of this problem, but the one I'll be doing comes from LeetCode. The problem: Given an array of integers, return the indices of the two numbers that add up to a given sum.

```
Input: nums = [2, 7, 11, 15], sum = 9
Output: [0, 1]
Because nums[0] + nums[1] = 2 + 7 = 9
```

I always like to start out with the most obvious brute force solution in order to make sure I have a good understanding of the problem. So my first solution was to simply use two nested for loops to check each combination of numbers. If adding the two numbers together equalled the given sum, then return the indices of those two numbers. If there's no combination, return an empty array.

```
var twoSum = function(nums, sum) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === sum) {
return [i, j];
}
}
};
return [];
};
```

Now I learned long ago that nested for loops have a runtime of O( n^{2} ), which is not ideal. There's pretty much always a better, more efficient way, and it usually involves an object/hash table/dictionary/whatever your programming language of choice calls it.

After thinking on this for a minute, I realized that I can iterate through the array and save each number and its index in an object, giving me this:

```
// given nums = [2, 7, 11, 15]
obj = {2: 0, 7: 1, 11: 2, 15: 3}
```

While building this object, I can check to see if the current number's complement (the sum minus the current number) already exists in the object. To make it a little easier to read, I saved this target number to a variable.

```
let target = sum - nums[i];
if (obj.hasOwnProperty(target)) {
return [obj[target], i];
}
```

This way, if the two numbers are near the beginning of the array, we don't even need to check the rest of the array and can return. This solution gives us time and space of O(n), which is twice as fast as using nested for loops. The final solution looks something like this:

```
var twoSum = function(nums, sum) {
let obj = {};
for (let i = 0; i < nums.length; i++) {
// save target number to variable, easier to read
let target = sum - nums[i];
// if the object has a key of the target number
// return its index (the value) and current index of nums
if (obj.hasOwnProperty(target)) {
return [obj[target], i];
}
// otherwise, create key value pair of the current number and its index
obj[nums[i]] = i;
}
return [];
};
```

Thanks for tuning in, and I'll catch you next week!

Awesome step by step Claire! :)

I just tried out this problem on Leetcode last night! I thought about introducing an object to solve it but never got around to trying it out. I really like your solution though! Great job, Claire!