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
numsever be anything other than an array of numbers? - Can
totalever be anything other than a number? - Will there always be two numbers in
numsthat add up tototal? 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
numsand iterate through each of the remaining elements of the array, checking if they add up tototal - move on to the second element of
numsand iterate through each of the remaining elements, checking if they add up tototal - 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]];
}
previousValues.add(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.
Top comments (8)
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.
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.
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:
Could also hack out things like, if the total is positive, don't check two negatives.
Hmm, I’m not quite following. When is this reduced to a list of unique numbers?
Oh, I totally misread your code. I think when I read you were using
new Set()you were callingnew Set(nums)to reduce the length of the list you had to process. My bad.Does this work with negative numbers?
Sure, why not?
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.