The Startup
Published in

The Startup

Two Ways to Solve the Two Sum Problem

Using both brute force O(n²) and a more elegant linear O(n) solution

This problem (or its variations) has been making the rounds in both Leetcode and HackerRank recently. In this post, I’ll offer two solutions to the problem. First, we’ll tackle what ought to be the most straight-forward solution, which if asked in an interview would probably be the thing that comes to mind first. Then, I’ll offer a more time-efficient solution that would be the answer to the likely follow-up question by the interviewer if you offered the first solution: can we do better?

The problem statement is simple: Given an array of integers, return indices of the two numbers such that they add up to a specific target. We can assume that each input will have exactly one solution, and we can’t use an element more than once. So, if our array is [2, 7, 11, 15] with a target of 26, the correct result would be [2, 3], because element 2 (11) plus element 3(15) equal 26. Let’s dive into the solutions below.

This first solution is what’s called the brute force solution. It’s referred as brute force because they tend to be easy to implement and will almost always find a solution, if there is one, by trying every possible answer. Because of this, they might take a very long time. Here’s that first solution:

function twoSum(nums, target) {for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
}

This algorithm takes the array (called nums) and iterates through it with nested for loops. This is what happens in the first iteration using our example:

  • i is set to 0, j is set to i + 1 (because we know we can’t use the same element twice)
  • We check to see if our condition is met: is nums[0] + nums[1] = 26? 2 + 9 26, so we continue the loop by incrementing j…
  • is nums[0] + nums[2] = 26? 2 + 11 26, so we continue the loop by incrementing j…
  • is nums[0] + nums[3] = 26? 2 + 15 26, so we continue the loop by incrementing i as we’ve reached the end of the array without a solution, and starting j at i +1…
  • is nums[1] + nums[2] = 26? 7+ 11 26, so we continue the loop…

I think you see the pattern here. Eventually, when i = 2, and j =3, the if statement will evaluate to true, and return those positions in the form of an array.

As you can see with an array of only 4 elements, it’s a lot of iterations to find the solution. In fact, it would take the number or size of the elements of the array, squared! Minus 1 since we’re adding one iteration. Thus, the time complexity of the algorithm is O(n²). That’s the red line in the graph below, and takes exponentially longer time compared to other algorithm’s time as the size of our array increases.

This is considered bad. Can we do better? Let’s dive into an O(n) solution below.

function twoSum(nums, target) {
let numObj = {};
for (let i = 0; i < nums.length; i++) {
let complement = target - nums[i];
if (numObj[complement] !== undefined) {
return [numObj[complement], i];
}
numObj[nums[i]] = i;
}
}

Typically when we compare one algorithm’s paradigm to another, there will be a tradeoff. In this case, the tradeoff is space. In order to make it faster, I’m going to create a new object in memory. We initialize an object, or hash map, called numObj. We then iterate as before, but only once, and with an additional variable called “complement”. This will be the number that I must have seen before that if added to the number I’m currently iterating would equal the target. Let’s walk through it with our array: [2, 7, 11, 15]

  • When i = 0, the complement will be 26 — nums[0], or 26–2 = 24.
  • Then the interesting thing happens. The algorithm asks, if that number (24) is not undefined in the numObj. In other words, have we seen it before, and does it exist in that object as a key? Since we haven’t seen it before, the if statement evaluates to false, and we continue.
  • We then add nums[i], which is 2, with a value of 0 in numObj, which was the index it had in the array.
  • When i = 1, the complement will be 26 — nums[1], or 26–7 = 19.
  • Is 19 undefined in the numObj? It is, so we add it with a key of 7 (the element in the array), and value of 1 (the index 7 has in the array).
  • When i = 2, the complement will be 26 — nums[2], or 26–11 = 15.
  • Is 15 undefined in the numObj? It is, so we add it with a key of 11(the element in the array), and value of 2(the index 11 has in the array).
  • When i = 3, the complement will be 26 — nums[3], or 26–15 = 11.
  • Is 11 undefined in the numObj? It is not. We saw it in the previous iteration. The statement now evaluates to true. So we return the value of the key of 11 in the numObj, which is 2, along with i, which is 3. And that’s our answer.

While harder to conceptualize, you see that this algorithm take a lot less iterations. In fact, at worse, only as many iterations as the size of the array, giving us an O(n) time, or the blue line in the graph above. Much better!

Thanks for reading!

And remember: grit > talent.

--

--

--

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +756K followers.

Recommended from Medium

Use API To Categorize Spanish Websites

Oracle data (ETL) to Google BigQuery using Google Cloud Dataflow and Dataprep

Classier solution for Ruby file uploading— CarrierWave

Udacity Android Developer Nanodegree: Behind The Scenes!

Introduction to Microservices | සිංහලෙන්

How To Distinguish Between Home Computer and Server?

Automate your iOS apps using Bitrise

Get Antimony Real-Time Rates In Seconds With An API

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Saul Feliz

Saul Feliz

Always learning.

More from Medium

Two Interns, a Junior and a FullStack project.

React Life Cycle Hooks

Handling Imposter Syndrome as a New Graduate Developer

Jack of all Trades Or Master of One: Which One Are You?

career track