Breaking Down DSAs: Two Sum

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!

Comments

[Lily]

Hi Claire! I am new to coding and recently learning Javascript and I wanted to get practicing on algorithm questions asap, so I started with the supposedly easy challenge "Two Sum". I am struggling with understanding why my brute force solution isn't producing the expected result and wondering if you could provide some guidance for me? I want to enhance the solution once I understand why my first solution isn't working. Here's my code snippet:

function twoSum(targetSum, array) {
var indicesTracker = [];
var sum;

            for (var i=0; i < array.length; i++) {

                for(var j=1; j < array.length; j++) {

                    sum = array[i] + array[j];

                        if(sum == targetSum) {

                        indicesTracker.push([i,j]);

                        }
                }
            }

            return indicesTracker;
        }

I put this code on an editor and ran it through the browser and when I called the function, I showed up correctly on the console but I can't get it to work on LeetCode. Been struggling since yesterday and still can't figure out why...

The above code gives an output of [], but I've added the indices to my indicesTracker array though, so I don't understand what's causing the wrong answer.

Your help would be greatly appreciated!
Lily

[Claire Muller]

Hey! Great work, just a few things:

1. There's a small but important error in your second for loop: j is set to 1, it should be i+1. This way you're always comparing i with the element that follows. The way it is now, every time i increases, j is set back to 1.

2. Once your function finds a match (sum == targetSum), you're pushing an array into the indicesTracker array, so your function is returning a nested array: [[i, j]]. You can simply push the elements themselves.

3. Your function also keeps going even after it finds a match. As it is now, given targetSum = 9, and array = [1, 7, 3, 2, 6], your function will return [1, 3, 2, 4].

Let me know if this helped or you have any other questions! I also highly recommend this site for visualizing what's going on in your functions, it's helped me a ton: pythontutor.com/javascript.html#mo...

[Lily]

Thank you so much for the clear explanation Claire! Really really appreciate it! It all makes more sense now! I've also started using the link you suggested and is trying to understand how it works ! :D

[jassica]

hii i m stated larning javascript just ..... but i have in difficult in finding resourses of DSA in javascript can u please suggest me some website or utube which is best to start learning DSA codding question in javascript ...
i need help

[kcarrel]

Awesome step by step Claire! :)

[Jenny Shaw]

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!