Sum of 2

In the spirit of learning more about Data Structures and Algorithms, let’s do a quick run through of a problem from LeetCode that is ranked as easy.

Problem Statement

• Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
• You may assume that each input would have exactly one solution, and you may not use the same element twice.
• You can return the answer in any order.
• Example:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Determining the Desired Outcome

So, we should determine a few things before approaching this problem.

First, what are the inputs? In this case, we are given an array, nums. Additionally, we are given a target, which represents the sum of two numbers in the nums array. Pretty straightforward so far.

Next, we want to know what the output should be. In this case, we want to return an array that contains the indices of the elements in the nums array that add up to the target. This is an important distinction — we want the indices, not the values themselves.

Problem Setup

Let’s set up the problem with the inputs and outputs. We already know that our function accepts an array, nums, and outputs a second array, result, that contains the indices of the values that sum up to target.

In this case, the first thing that we want to do is initialize our result array, which will be returned at the end of the function. Here’s what that should look like:

Not so bad so far, right?

Strategizing

Now, we can focus on how to approach this problem. We can tell from the nature of the problem (we are given an array) that the solution will involve some form of iteration. So, let’s see what that should mean.

First, we need to iterate starting from the beginning of the array. The simplest way to do this is with our old friend, the for loop. Let’s see what this should look like.

However, this only gives us access to one element at a time, and we need to find a second element in order to reach the target. This is where we step it up a notch.

We need a second for loop that loops over the remainder of the elements. By using a nested loop, we can compare the values of i and j to the target, and then, somehow, return them as an array. So, let’s see what this should look like.

Now, we have what we need to execute the solution.

Putting the Pieces Together

Now that we have our nested loop, and we know that we have to loop through the array using a nested loop, we have to determine what we want to compare in order to reach our solution.

In the problem statement, we know that we are given a target. In this example, the target is 9. So, looping through the array above, how do we determine which two elements that add up to 9? Simple: we add them.

We need a simple conditional statement to check each pair of elements against the target. If there is a match, then we add the indices of these elements to our result array. Due to the fact that this problem states that there must be a match, we do not have to handle any additional edge cases.

Let’s loop through!

Awesome! Now, we just need the last piece!

The Final Step

So, we have a problem that reaches a result when, not if, meaning that we know that there is a matching pair; it’s just a matter of finding it. We accomplished this in the last section.

The last thing that we have to do when we find the solution is add the two indices to the array. We can do this with the push method. Here’s how it should look:

And that’s it, ladies and gentlemen!

The Big O

Whenever we are dealing with nested for loops, there is a pretty good chance that the Big O (runtime complexity) will be O(n²). That is exactly the case here.

As we add elements to the array, the number of operations will increase exponentially. This solution is OK when we have a relatively small array, but imagine looping through an array of 10,000 elements twice! Not ideal, but, it is what it is.

I hope that you enjoyed this walkthrough. As always, Happy Coding!