DEV Community

Nick Scialli (he/him)

Posted on

Exploring the Two Sum Interview Question in JavaScript

The two-sum interview question is interesting to explore because it has both a brute force, logical solution, as well as a more time-efficient solution that can demonstrate strong computer science fundamentals. Let's explore both potential solutions and hopefully learn along the way!

The Two-Sum Question

First, let's understand the two-sum question. It's usually posed as some form of the following:

You are asked to create a function that takes two parameters. The first parameter, `nums`, is an array of numbers. The second parameter, `total` is a single number. The output of the function should be a two-element array that represents a pair of numbers in `nums` that add up to `total`.

``````/**
* @param {number[]} nums
* @param {number} total
* @return {number[]}
*/
const twoSum = (arr, total) => {
// Solution here
};
``````

Typically, we're given a couple examples of valid input/output combinations:

``````input: nums = [1, 2, 3], total = 4
output: [1, 3]

input: nums = [3, 9, 12, 20], total = 21
output: [9, 12]
``````

A Quick Note on Solving Coding Challenges During an Interview

If you're solving any coding challenge during an interview, it would be prudent to ask some clarifying questions before you start solving the problem. In the two-sum case, you might want to ask the following questions (and probably some others I can't think of):

• Can `nums` ever be anything other than an array of numbers?
• Can `total` ever be anything other than a number?
• Will there always be two numbers in `nums` that add up to `total`? If not, what should the output be when there is no solution?

For the purpose of this blog post, we will assume `nums` will always be an array of numbers, `total` will always be a number, and there will always be a solution to the problem (i.e., two numbers in `nums` will always add up to `total`).

Brute Force the Solution

Our first instinct will likely be to brute force the solution. To do this, we can use the following procedure:

• start with the first element of `nums` and iterate through each of the remaining elements of the array, checking if they add up to `total`
• move on to the second element of `nums` and iterate through each of the remaining elements, checking if they add up to `total`
• repeat until the matching sum is found!

In code, we'll implement this as a nested loop:

``````/**
* @param {number[]} nums
* @param {number} total
* @return {number[]}
*/
const twoSum = (nums, total) => {
for (let i = 0; i < nums.length - 1; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === total) {
return [nums[i], nums[j]];
}
}
}
};

console.log(twoSum([1, 2, 3], 4)); // [1, 3]
console.log(twoSum([3, 9, 12, 20], 21)); // [9, 12]
``````

Awesome! There are a couple potentially tricky aspects of this solution; let's quickly explore them.

Why does the outer loop stop at `i < nums.length - 1`?

The outer loop doesn't have to account for the last element of the `nums` array, just the second-to-last element of the array. The nested loop will account for the final element.

Why does the nested loop start at `j = i + 1`?

As we described above, the outer loop starts at one position in the array and the inner loop only needs to start with numbers occurring later in the array. Any combinations including earlier numbers in the array have previously been attempted.

The Problem with the Brute Force Approach

Solving two-sum the brute force way is great. It demonstrates solid reasoning and coding skills. That being said, it's helpful to be able to articulate what's wrong with any solution: awareness of your software's limitations and the associated computer science fundamentals is both impressive to prospective employers and important as you grow as a developer.

So what's the problem? Nested loops open us up to O(n2), or quadratic, time complexity.

Understanding O(n2) time complexity

Essentially, O(n2) time complexity means the time to execute the algorithm is proportional to the square of the number of inputs. This becomes obvious when we look at our brute force approach: if we add an element to `nums`, our solution has to go through an additional element in each of the nested loops and then has to do an additional time through the entire double loop.

Let's do an experiment to see this add up. We will create an array with 100,000 elements with the solution nums being the final two elements.

``````const len = 100000;
const bigArr = new Array(len).fill(1);
bigArr[len - 2] = 9;
bigArr[len - 1] = 10;
const total = 19;
``````

Now lets implement our brute force two-sum solution, but this time we'll keep track of how many iterations it takes as well as roughly how long it takes.

``````const { performance } = require("perf_hooks");

const twoSum = (nums, total) => {
let iterations = 0;
const startTime = performance.now();
for (let i = 0; i < nums.length - 1; i++) {
for (let j = i + 1; j < nums.length; j++) {
iterations++;
if (nums[i] + nums[j] === total) {
console.log(
`Iterations: \${iterations}`,
`Time: \${performance.now() - startTime}ms`
);
return [nums[i], nums[j]];
}
}
}
};

twoSum(bigArr, total);
// Iterations: 4999950000 Time: 20032ms
``````

The brute force solution went through almost 5 billion iterations and, on my computer, took 20 seconds. Yikes! Let's see if we can do better.

The Power of Objects (and, More Importantly, Hash Tables)

We can, in fact, do better. Rather than creating a nested loop, let's just go through the `nums` array once. To keep track of the array elements we've already seen, we're going to add them as keys to an object. For each element of the array, we check if the complementary key exists in our object.

That may have been confusing in paragraph form, so here's the code!

``````const twoSum = (nums, total) => {
// Keep track of previous array values
const previousValues = {};

for (let i = 0; i < nums.length; i++) {
// What previous value needs to exist for
// us to have found our solution?
const complement = total - nums[i];

if (previousValues[complement]) {
return [complement, nums[i]];
}

// This current array item now becomes
// a previous value
previousValues[nums[i]] = true;
}
};

console.log(twoSum([1, 2, 3], 4)); // [1, 3]
console.log(twoSum([3, 9, 12, 20], 21)); // [9, 12]
``````

You may be thinking: we only have one loop, sure, but our second loop is replaced by this `previousValues[complement]` lookup. Is that really so much more efficient than a second loop?

The answer is yes because object lookup is O(1) time complexity. This is due to JavaScript's use of hash tables in objects!

Since the object lookup is O(1) and the loop is O(n), our functions time complexity is now O(n). Let's try our new algorithm out on the same big array we used before.

``````const { performance } = require("perf_hooks");

const len = 100000;
const bigArr = new Array(len).fill(1);
bigArr[len - 2] = 9;
bigArr[len - 1] = 10;
const total = 19;

const twoSum = (nums, total) => {
let iterations = 0;
const startTime = performance.now();

const previousValues = {};
for (let i = 0; i < nums.length; i++) {
iterations++;
const complement = total - nums[i];
if (previousValues[complement]) {
console.log(
`Iterations: \${iterations}`,
`Time: \${performance.now() - startTime}ms`
);
return [complement, nums[i]];
}
previousValues[nums[i]] = true;
}
};

twoSum(bigArr, total);
// Iterations: 100000 Time: 4ms
``````

Much, much faster.

Nothing's Free

While we decreased our time complexity, we increased our space complexity since we need to create a new object, `previousValues`, in memory. For very large objects (e.g., on the order of a million elements), we're talking about 10MB of memory. Not trivial, but likely worth it to save on time complexity!

A More Idiomatic Approach

JavaScript actually has a specific object to that would help with this problem: `Set` Object [1]. `Set` is "more idiomatic" because it's a mechanism to store unique values (or object references) without having to do the weird `previousValues[nums[i]] = true;` workaround I did above.

If we change our implementation to use `Set`, it might look as follows:

``````const twoSum = (nums, total) => {
const previousValues = new Set();
for (let i = 0; i < nums.length; i++) {
const complement = total - nums[i];
if (previousValues.has(complement)) {
return [complement, nums[i]];
}
}
};
``````

According to the the EcmaScript 2015 spec, "Set objects must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection" [2]. So, we're not necessarily sure `Set` will be implemented using has tables, but we can be confident of its efficiency.

Conclusion

There are multiple ways to solve the two-sum problem in JavaScript. If you find yourself facing this question in an interview, consider flexing your data structure knowledge by offering a solution with hash table efficiency by either using an Object to store results or the JavaScript `Set` object!

References

For a great primer on hash tables, see this excellent post.

Jim Burbridge

One other thing that I've seen come up with this problem is an interviewer telling me that I could assume that the given array was already sorted. I said well that's interesting, usually I get told that it's unsorted so you can never be sure. You can make some weird search algorithms using the idea that the array is already sorted. I can't remember exactly what I did but I think it was a rough binary search from there.

The interviewer asked "what would you do if the array wasn't sorted then?" I looked at the board and went "sort it first, before passing it to the function." We both had a good laugh.

Nick Scialli (he/him)

Ha! Well that also says a lot for interviewing skills of asking clarifying questions and explaining your thinking. You definitely have to display technical skills, but at the end of the day you have to convince the interviewer that they'd want to work with you.

Ben Sinclair • Edited

Reducing this to a list of unique numbers would fail on ([1,2,2,5], 4) because though 2 + 2 == 4, it'd never get checked.

I think I'd do this by something like:

• set half = total / 2
• if half is in list more than once, return [half, half]
• else make it a set, sort the list, and then brute force much as before

Could also hack out things like, if the total is positive, don't check two negatives.

Nick Scialli (he/him)

Hmm, I’m not quite following. When is this reduced to a list of unique numbers?

Ben Sinclair

Oh, I totally misread your code. I think when I read you were using `new Set()` you were calling `new Set(nums)` to reduce the length of the list you had to process. My bad.

Theofanis Despoudis • Edited

Does this work with negative numbers?

Eugene Karataev

Sure, why not?

Eugene Karataev

Great example of iterative approach to solve a problem.
"Hash table" is the first thing that pops up in my mind when I try to optimize a brute-force solution.