Solving the Most Common Tech Interview Question
Three algorithm approaches with sample Python code
If you’re doing tech interviews, then you will definitely encounter the Two Sum problem at some point.
It is one of the most, if not the most, common algorithmic questions to be asked during technical interviews.
Given an array of integers, return the indices of two numbers such that the numbers add up to a specific target number.
Despite being a seemingly simple problem, there are multiple approaches you can take, each with their own pros and cons.
Understanding these approaches and being able to explain their differences signals to your interviewer that you have a strong grasp of CS fundamentals.
Approach 1: Naive Method
The first approach is the simplest one, and is probably how you would initially solve the problem without taking a moment to think of optimizations.
You just iterate over all possible pairs of numbers and return the first pair that adds up to your desired sum.
This approach runs in O(n²) time and O(1) space, where n is the length of
Approach 2: Time Optimized
The next approach improves on the time complexity by using extra space.
You start by initializing an empty map, which will be used to store previously-seen elements and their indices.
Then, for each element in the list, you first check if you have seen
sum_val - current_element previously by checking if it is in your map’s key-set. If so, then you have found your desired pair, since
current_element + (sum_val - current_element) == sum_val .
Otherwise, you add
current_element to your map and move on to the next element.
This approach runs in O(n) time and O(n) space. We assume that map lookups are O(1) operations, in the case of the map being a hash map.
Here, we only visit each array element once, since we cache previously seen elements and their indices in our map.
Approach 3: Space Optimized
The final approach improves on time complexity without using additional space, but still uses more time than approach 2.
In this method, we will first sort the array and use properties of a sorted array to improve our time complexity without needing to use auxiliary space.
To do this, we will use a two-pointer method. We start one pointer at the first element and the second pointer at the last element. We then check the sum of the two elements pointed to by those pointers.
If the sum is too high, then we decrement the second pointer which decreases the sum, and if the sum is too low, then we increment the first pointer which increases the sum.
We can only use this approach because the array is sorted, so we can guarantee that the array is non-decreasing.
This approach runs in O(n * log(n)) time and O(1) space. This assumes that we use a sorting method that runs in O(n * log(n)) time and O(1) space, such as heapsort.
Note that the dominating factor in this method’s run-time is from the
sort operation. Only O(n) comparisons are made afterward, as the pointers move by 1 each time and only move until they would overlap.
Here, we improve on the time complexity of the naive solution without needing to use additional storage like approach 2. We are able to leverage the fact that the array is sorted to minimize the number of comparisons that we must make.