Two Sums

I will be starting a series of blog posts on Wednesdays where I break down and review common computer science interview questions so we can all work on our data structure and algorithm knowledge. Today we will start the series with what might be the most common coding interview question: Two Sums. The question goes like this.

“Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.”

We will be running these questions on LeetCode. If you want to try the coding interview question: Two Sums for yourself first, go to https://leetcode.com/problems/two-sum/.

We will be solving this problem is Java. It is important to think through these problems first, write some pseudo code on paper and try to come up with the most efficient solution.
*cough* don’t use two for loops *cough*

Code

Here is what the boiler plate method will look like for us:

• 

We will be using a HashMap for this solution. It is a very common data structure and seen frequently in interview questions. HashMaps have constant look up time, which we will be using to look for values as we iterate through our input array (nums).

While we are here, lets go ahead and create our return array and return it.

• 

So our basic algorithm will be this. We will iterate through our array and for each value we will check to see if we have already found a value that will sum the current value to the target value.
For the above example. We will look at 2 and try to find 9 (Target) — 2 (current value) = 7 (have we seen a 7 yet?). If we have seen the value we can save off those index’s. If have not we can save the value
of the current location into our HashMap (value,index) and move to the next value. Remember, we need to save the index for each value because the final array returned wants the indexed location of each value in the array, not the value’s that sum to the target.

Note: This solution is not technically the fastest but is easy to grasp conceptually.

So lets make the algorithm real by looping through our array.

Hash Maps

For each index we will look for the current values pair that sums to target. If we find it, we can get the index of the paired value from our map and the current index and add them to the res array we are returning.

If we do not find the paired value to sum to our target, we can add the value and index of our current record to our map. This way we can remember that we have come across this value later.

Tests

We can submit our code and see the results. When submitting code on LeetCode a variety of test are run against your code to hit all edge cases. Success! We passed, and now have a valuable tool in our belt: HashMaps.

Here is a video explaining the logic behind this problem:

https://www.youtube.com/watch?v=wpUZRppjab8&feature=emb_logo

For more tech blogs, subscribe to the code_marks news letter: http://eepurl.com/gZCMQz

Check out the next interview  question!