AlgoDaily - Two Sum

Good evening! Here's our prompt for today.

This is a classic and very common interview problem. Given an array of integers, return the indices of the two numbers in it that add up to a specific "goal" number.

Suppose we had an array [1, 3, 6, 7, 9], and let's say our "goal" number was 10. Our numbers to sum to it could be 3 and 7, and we would return an array of indices 1 and 3 respectively.

1let arr = [1, 3, 6, 7, 9];
2let goal = 10;
3twoSum(arr, goal);
4// [1, 3]

You may assume that each input would have exactly one solution. Additionally, you may not use the same element twice towards the sum. This means if given [1, 3] and a goal of 2, you cannot use 1 twice and return its index twice as [0, 0].

Note that you cannot guarantee the array is sorted.

AlgoDaily partner CodeTips.co.uk has kindly provided a guide on solving Two Sum in Go. Check it out for even deeper coverage of this problem.

Constraints

Length of the array <= 100000
The values of the array will be between -1000000000 and 1000000000
The array can be empty
The target sum will be between -1000000000 and 1000000000
Expected time complexity : O(n)
Expected space complexity : O(n)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx
 
var assert = require('assert');
​
function twoSum(arr, goal) {
  const results = [];
  // define this method
  return results;
}
​
try {
  assert.deepEqual(twoSum([1, 9, 13, 20, 47], 10), [0, 1]);
​
  console.log(
    'PASSED: ' + 'assert.deepEqual(twoSum([1, 9, 13, 20, 47], 10), [0, 1]);'
  );
} catch (err) {
  console.log(err);
}
​
try {
  assert.deepEqual(twoSum([3, 2, 4, 1, 9], 12), [0, 4]);
​
  console.log(
    'PASSED: ' + 'assert.deepEqual(twoSum([3, 2, 4, 1, 9], 12), [0, 4]);'
  );
} catch (err) {
  console.log(err);
}
​
try {

Tired of reading? Watch this video explanation!

To change the speed of the video or see it in full screen, click the icons to the right of the progress bar.

We'll now take you through what you need to know.

How do I use this guide?

Run through a few examples and notice we immediately grasp for two things-- we need to iterate and we need to compare. A simple brute force solution would be to try every single pair in the array and check it against the goal number.

We can do this via a nested for-loop, with the outer loop iterating through all elements in the array. The inner loop would check the outer loop's current element against every other element, and see if they add up to the target.

Pseudocode as follows:

SNIPPET

1for num in nums:
2  for otherNum in nums:
3    if num + otherNum == target:
4      return true
5return false

This may be fine if our input is small, but this grows quite fast, as every additional element in the input will require a number of operations equivalent to the input length. The time complexity would be O(n^2). A better methodology is to use a data structure-- specifically, a hash map.

Using a hash map, we can set up a separate tracker, where the keys represent the difference between the goal and a number at an index.

The above is a visual of a hash map data structure.

So if we had an array of numbers [1, 3, 5], and the target/goal was 4, here's the example hash map that we'd generate:

xxxxxxxxxx
 
const arr = [1, 3, 5];
const goal = 4;
​
const hash = {
  3: 0,  // 4 - 1 = 3 at index 0
  1: 1,   // 4 - 3 = 1 at index 1
  -1: 2  // 4 - 5 = -1 at index 2
}
​
console.log(hash);

The hash above represents a record of elements we've seen so far that can be looked up via their difference from the goal. We can then use that information in subsequent iterations to find a matching pair, since we can try to look up arr[i] in the hash.

In the above example of [1, 3, 4], we only need two iterations!

At index 0, we encounter 1.
Calculate the difference between goal - arr[i]. 4 - 1 = 3
Take the difference of 3 and store it in our table. hash[3] = 0 (we store the index)

As soon as we get to index 1 and see 3, we can:

Look up 3 in the hash map
Retrieve index 0

So we know that 1 (index 0) and 3 (index 1) pair sum to 4. We return [0, 1].

The time complexity of this solution is O(n) because we iterate through all the elements exactly once. Space complexity is similarly O(n) as the hash map will grow proportionate to the input.

Two Pointers

Notice that the question prompt explicitly said that the input array may not be sorted. But what if it was guaranteed to be sorted? How can we use that property to help us?

If you've checked out the two pointers tutorial, you might have a guess at how we'll approach this.

See, if the input array is sorted as such:

[1, 2, 3, 4, 6, 7]

And, say we had to find two numbers summing up to 6-- instead of testing every pair, we can start with a pair, and then get information about how close or far we are from our goal. Using that information, we know whether we need smaller numbers (sorted array, so we can go left) or larger numbers (sorted array, so we can go right).

xxxxxxxxxx
 
const nums = [1, 2, 3, 4, 6, 7];
const goal = 6;
​
function twoSum(nums, goal) {
  let start = 0;
  let end = nums.length - 1;
​
  while (start <= end) {
    const curr = nums[start] + nums[end];
​
    if (curr > goal) {
      end -= 1;
    } else if (curr < goal) {
      start += 1;
    } else {
      return [start, end];
    }
  }
​
  return [];
}
​
console.log(twoSum(nums, goal));

One Pager Cheat Sheet

Given an array of integers and a target number, find the indices of the two numbers which add up to the target, without using the same element twice and providing a solution with an expected time complexity of O(n) and an expected space complexity of O(n).
We can solve this problem by iterating through each element of the array and comparing it against every other element, using a nested for-loop.
We can reduce the time complexity from O(n^2) to O(n) by using a hash map to keep track of the difference between the goal and values at each index of our input array.
The time complexity of this O(n) solution is O(n) and has an equal space complexity, as we can iterate through the elements once and store them in a hash map.
We can use Two Pointers to efficiently traverse through a sorted array and find a pair of numbers that add up to a given sum.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx
}
 
var assert = require('assert');
​
function twoSum(arr, goal) {
  const results = [];
  const hash = {};
​
  for (let idx in arr) {
    const difference = goal - arr[idx];
    if (hash.hasOwnProperty(arr[idx])) {
      results[0] = parseInt(hash[arr[idx]]);
      results[1] = parseInt(idx);
    } else {
      hash[difference] = idx;
    }
  }
​
  return results;
}
​
try {
  assert.deepEqual(twoSum([1, 9, 13, 20, 47], 10), [0, 1]);
​
  console.log(
    'PASSED: ' + 'assert.deepEqual(twoSum([1, 9, 13, 20, 47], 10), [0, 1]);'
  );
} catch (err) {
  console.log(err);
}
​
try {
  assert.deepEqual(twoSum([3, 2, 4, 1, 9], 12), [0, 4]);
​

Got more time? Let's keep going.

If you had any problems with this tutorial, check out the main forum thread here.