How to Solve Two Sum in an Interview

The best way to solve Two Sum in an interview is to use the Two Pointers strategy to implement a brute force (O(N^2)) solution, followed by adding a Hashmap to optimize your run-time complexity to O(N).

Two sum, like many array and linked-list problems, requires the Two Pointers strategy. The name is self explanatory: reference two points in a data structure to analyze. Let’s show an interviewer how we would begin thinking about the problem.

On a whiteboard (or comments if you’re in an online interview), show your base test case, and some initial thoughts. This should be a quick and engaging process with your interviewer. For Two Sum, visually show your pointers through 2 or 3 iterations.

I’ve demonstrated many iterations to help illustrate what the algorithm is doing. This is a brute force solution, but with a twist: the second pointer is always ahead of the first, making the actual code of the algorithm slightly different than a classic brute force approach. Before you begin coding, it may also be helpful to ask how to handle edge cases - like how to handle there being no solution for the input. Now that we have the concept in our heads, let’s code.

Writing brute force for-loops should be automatic. It’s a basic leetcode tool you need to have in your belt when approaching interviews. I’ve made the variable names more specific to match the concept we wrote out in the comments. Your code is now more readable and organized, so your interviewer may appreciate that. Now that we have a brute force solution, your interviewer will likely ask you to improve your code.

Like many optimizations of problems, Two Sum is best optimized with a hashmap. Hashmaps are most effectively used to remember, or “cache” data we’ve already seen before. To engage your interviewer, it may be a good idea to first suggest this as a potential data structure for optimizing this problem.

Typically, I assume that there’s a one-pass O(N) solution, but it will still be helpful to ask your interviewer if there is one (they already know the answer). Getting to the optimal solution will likely take some back and forth with your interviewer. Remember to walk through each step of your thinking.

Two pointers is probably not the most efficient solution because we are pointing at the same data multiple times - it’s redundant. Is there a way we can point at each data point once (O(N))? Your interviewer will likely not say much, but it’s okay to proceed thinking forward anyway.

Mention that our hashmap is going to help us remember something each step of the way, effectively taking the role of the second pointer. What information is helpful? Is the index helpful? Yes, we need to return an index as the final solution, so that will be helpful. Is the value important? Sort of. It’s helpful in relation to the target sum. It’s so simple, but I will rearticulate the solution: value1 + value2 = targetSum. Rewritten it’s: targetSum - value1 = value2. We are solving for value2. If value1 is the value at the current index, and because we are only using one pointer now, the thing we will have to remember is the index and value2. Why? We know that if we find value2, then adding value1 will create targetSum! So the thing we should store as the key in our hashmap is value2 - the number we’re trying to find, and the index of value1. Let’s show the comments.

Visualizing your thinking is so helpful for you and the interviewer. As we can see, each element is storing its other half (complement) value and the index. With that, you can write out your code.

Complement may not have been the word or concept you came up with when thinking about this problem. I think it’s not the most intuitive, so a variable name like “otherHalf” would have been fine - your interviewer will correct you if they have a problem with it.