The two sum problem is a classic coding challenge required in many tech interviews, and the #1 challenge on leetcode.com.
Usually, one is given an unsorted array of integers and a target integer. In this scenario, your goal is to write an efficient algorithm that returns if there are two elements in the array that add up to the target. You are required to either return the indices or the integers themselves.
The example in this post assumes that there will be an answer and there will only be one pair that sums up to the target.
In your potential interview, it is important that you specifically ask your interviewer if they would like you to return all pairs, only the first pair, or what they want you to return if there is no pair at all.
The Brute Force Solution
The "brute force solution" is the least efficient way of solving any problem. It has the worst time/space complexity–but, it is a solution. However, it is better than nothing if you are unable to come up with a more advanced approach, and you may score points by being able to be coached into the proper direction.
For this example, we are going to use nested loops. There is an outer loop that iterates through every element and an inner loop to find two elements that sum up to k.
The time complexity of this approach is O(n^2). As an example: If there are 100 elements in the array, you iterate 100 * 100-1, in short 100^2 or O(n^2).
Now, let's look at a more efficient solution. Efficiency is important when considering scalability. For example, the array could contain thousands or millions of elements.
Hash Map for a Linear Solution
Using a Hash Map, store every element of the array in the map and check if there is an element in the map/dictionary that–with the element at current index–sums up to k.
This is the best solution with a linear runtime. At most, we are checking every element once. The downside of this solution (which your interviewer may ask) is, that it requires O(n) space, given that we potentially need to store every element in the dictionary/hash map.
We can always buy more space... We can always buy more memory... but we can't buy more time.