Breaking Down DSAs: Two Sum
Tags: algorithms, javascript, learning, programming
Published: 2019-08-04 17:21:11

---
title: Breaking Down DSAs: Two Sum
published: true
description: 
tags: algorithms, javascript, learning, programming
---

Another week, another blog post! I really enjoyed writing my [last post](https://dev.to/clairemuller/breaking-down-dsas-valid-anagram-1m55) 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](https://leetcode.com/problems/two-sum/). 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.

```javascript
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:

```javascript
// 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.

```javascript
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:

```javascript
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!