One popular question that may be thrown at you in a technical interview is known as the two-sum problem. For example, the two sum has been known to appear in Facebook and Google interviews. It was also the first LeetCode problem that I successfully solved with all test cases passed. Fortunately, my relentless technical interview prep journey began with the two sum!
The two-sum problem is a LeetCode classic that consists of different fundamental solutions. Constructing these solutions involves understanding different techniques that I will discuss further in just a moment. Before continuing, however, I recommend that you brush up on arrays, hash maps, time-complexity, and space-complexity in order to fully understand the problem. GeeksForGeeks has some well-written articles on different interview problems and concepts and is a great resource for this study. So, let’s dive into this problem now.
What Is the Two-Sum Problem?
- Given an array of integers, return indices of the two numbers such that they add up to a specific target.
- Note that you cannot use the same element in the array twice, but you can assume that there will only be one solution for each test case.
Example Test Cases
- Input: nums = [1,4,10,-3], target = 14
- Output: [1,2] or [2,1] # 4 + 10 = 14
- Input: nums = [9,5,1,23], target = 10
- Output: [0,2] or [2,0] # 9 + 1 = 10
- Input: nums = [1,-2,5,10], target = -1
- Output: [0,1] or [1,0] # 1 + -2 = -1
As you can see from the test cases above, the output returned in each is an array of the indices of the two numbers that add up to the target. Note that the order of the indices that are in the solution array is not important for this problem. Now, let’s take a look at the different solutions to the two-sum problem using Python3.
First Approach
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i,j]The solution seems simple enough, right? We have a nested for-loop where we look for the first pair of indices of two numbers that add up to the target value. Even though this approach is as simple as it gets, is it the most optimal? Let’s have a look at the time and space complexities below.
- Time Complexity: O(n²)
- Space Complexity: O(1)
At first glance, you can see that this solution is favorable in regards to space since the space complexity is constant. This is because this algorithm does not rely on any additional data structures such as arrays or dictionaries. Even as the input array can grow bigger for other test cases, it still isn’t using any extra space.
On the other hand, the time complexity of this solution is a cause for concern with an O(n²) run time. For each element in nums, this approach attempts to find its complement by iterating through the rest of the array that takes O(n) time. Although this approach may not make a difference when it comes to small inputs, it can have a drastic effect on the run time with larger inputs since time complexity is growing quadratically. So, always be aware of nested for-loops as these can be detrimental to the running time of your code!
A More Optimal Solution
def twoSum(self, nums: List[int], target: int) -> List[int]:
hash_map = {}
for i in range(len(nums)):
if nums[i] in hash_map:
return [i, hash_map[nums[i]]]
else:
hash_map[target - nums[i]] = iUnlike the previous solution, there is no nested for-loop used here, which will make a big difference in time complexity later on. We are now using a new variable, however: hash_map, which is a Python dictionary. We are using hash_map, which, as specified by its name, has a hash map data structure. We are storing each element in nums as keys where their corresponding values are their indices.
For each element that we iterate through in nums, we store their complements as keys in the hash map with their values being in the current index. Note that we’re only storing these key-value pairs if the current element is not a present key in our hash map. If the current element exists as a key, then we can return an array with the current index and its corresponding value in the hash map since this element was inserted in a previous iteration. Let’s now check out the time and space complexities of this new approach.
- Time Complexity: O(n)
- Space Complexity: O(n)
We have now improved the time complexity of our solution immensely with a run time of O(n). Each element is only being iterated once and only once because we’re no longer looping through the entire array for each iteration. Also, the lookup time to see if an element exists in our hash map is near-constant time because a lookup could take O(n) time if a collision took place in the hash map. As long as the hash function used by the hash map is chosen carefully where collisions are avoided, a lookup is amortized to O(1).
This improvement in performance comes at a significant cost, however. We now have a space complexity of O(n) as we’re now using a hash map in our solution as a storage buffer for our elements in the input. Now, we’re sacrificing space for speed. This is a perfect example of the space-time tradeoff because we can either increase space and decrease speed or vice-versa!
Tackle the Two-Sum Problem With Confidence
When tackling interview problems, it is crucial to keep space and time complexity in mind when developing a solution. Moreover, always ask yourself, “Can I do better?” every time you develop a solution to a technical problem so that you can improve the efficiency of your algorithm whether in speed or space improvements. No one wants to run a program that is very slow and uses a lot of memory; it is not efficient!
Now go give this problem a shot here. If you are given this question during one of your interviews, consider yourself very lucky as you now understand the problem on a deeper level!
