twoSum

The twoSum problem is an extremely popular interview problem and have had it come up in every algorithm meetup I have been to and have even actually had it as a mock interview question before. It's very common so if you are like me and are preparing for technical interviews, I would recommend mastering it.

First I'll break down the problem. Basically, you are given an array of integers, and a target number. Let's say the array is [5, 6, 3, 2, 11, -1, 2, 7] and our target is 16. We want to return the two numbers that add up to our target. In this case it would be [5, 11]. There are so many ways to accomplish this but I'll go through two. One being the "brute force" way which isn't the most optimal, and the other solution being a more optimal solution.

The brute force solution requires us to loop over our array using two pointers. Our first pointer will start at the 0 index, and our second array traversal pointer will start at 1 ahead of our first pointer. We then add a conditional to add up the value of our first pointer and the value of our second pointer. If those two pointers equal each other, we return the two pointers. If none of the values in our array add up to the target sum then what do we do? In an interview setting that would be considered an edge case, something you should ask the the person interviewing you for right off the bat. In this case, if we don't find two sums that sum up to the target we will return an empty array.

Let's break it down step by step, we start our first pointer traversal at 0. Inside of our loop we create a variable called current that we will use to keep track of the current number of our traversal. We then start our second traversal of the array starting our second pointer at i + 1. So if we had an array [1, 2, 3] the pointer i starts at index 0 (1) and j starts at index 1 (2). Then we create a variable to keep track of our second current iterator (secondCurrent). Literally all that is left here is a conditional to check if our current + secondCurrent is equal to our target and if it is, return both pointers return[current, secondCurrent]. As for the end, don't forget the edge case of returning an empty array if no integers add up to the target, this is very important.

Now, why is this a naive solution? Well we can optimize our code to make it run faster. The time complexity of the algorithm above is quadratic ( O(n2) ) which isn't the best solution. Unfamiliar with quadratic time complexity? Quadratic time complexity represents an algorithm whose performance is directly proportional to the squared size of the input data set (think of Linear, but squared). Within our programs, this time complexity will occur whenever we nest over multiple iterations within the data sets.

In an interview setting, after submitting that solution your interviewer will ask you if you can optimize your solution to make it more efficient, and you will say yes and this is how. By initializing an empty object (or hash table or whatever you prefer to call it) to store values in. Here is what the optimized solution looks like:

The difference here code wise is we set our currentNum variable similarly to how we did in the naive solution but then things get different. We calculate the difference of our target and our currentNum. Then say if our difference is in our nums object, then we return our currentNum, difference. If the difference isn't in our nums object then we take our currentNum and store it into our hash table. (nums[currentNum] = true ). Then, if no two integers add up to the target we of course return our empty array at the end.

We were able to optimize our time complexity to linear time (O(n)) where n is the size of the input. Informally, this means that the running time increases at most linearly with the size of the input. Linear time is the best possible time complexity in situations where the algorithm has to sequentially read its entire input in the worst case scenario.