Two Sum

What do we need to check

It is guaranteed to have two elements that sum up to the target value, and there is only one valid answer (we have only one pair that sums up to the target). The question asks us to return that pair of elements' indexes. And we cannot use the same element twice, we need two distinct indexes. These points are covered in the examples below with explanations.

Example Inputs & Outputs

Constraints

We have some constraints for both our inputs and also for our time and memory usage. For our time and space complexities, there is always a recommended boundary and it's a good practice to stay in that recommended boundary. Since these questions are designed to improve our knowledge and practice on data structures and algorithms, we don't just solve these questions, but we design optimized solutions.

For our inputs we know that our elements and target value are limited between -10,000,000 <= nums[i], target <= 10,000,000. Note that both array elements and our target could be some negative numbers.

Our input array's length is between 2 <= nums.length <= 1000. Note that we need at least 2 numbers if we are asked to return two distinct indexes.

For our recommended time complexity, question says that we could solve it with O(n) complexity, where n is the length of the array.

For space usage we could use at most O(n) space, that is, space usage should grow lineary with the size of the array.

Common Approaches

There are many ways to solve any problem in programming, but of course there are always some preferred solutions, and this problem is no exception for this rule. asddsffsdfsdfsdfsdfsdf However, I want to mention a few different approaches because if you don't get the actual solution at first, you could spend some time with other solutions to see the intuition behind the question's main idea. Also approaches are written in an order with a step closer to the actual solution, so it would be good practice to go through all of them step by step. We start with the most naive one, brute force.

Brute Force

Brute force is the most primitive solution for many problems. For Two Sum, you could calculate all of two-combinations of elements in the given array and when the sum of these combinations hits the target value, you could just return the indexes of those elements.

It would work, and actually it would cost us O(1) space, which is more than OK, but on the other hand, time complexity would be O(n²), which is not appropriate for the question's requirements.

Math Method

This is actually not a formal method, but I wanted to call it that. So, above we tried to search all pairs of elements, and this was the main bottleneck of our time complexity. What if we search for just one element? This is the main idea of this approach. Note that this approach won't improve our time complexity, but it's going to be helpful when it comes to the actual solution.

We know that there is only one valid pair, and so we could divide the target into two parts num1 and num2 where target = num1 + num2.

Instead of searching num1 and num2 at the same time, we could tweak the equation and fix one number here. That is, fix the first number to be num1, rearrange the equation like target - num1 = num2, and search for the target - num1 in the array, namely num2.

The idea is simple here, for each element at index i calculate difference=target-nums[i], loop through all of the remaining elements and if the difference is found, we return i and the difference's index.

Everything is OK, except that, for the second loop we are scanning the rest of the array to find the difference value, and this process executes until we find the actual pair. So our time complexity is going to be O(n²) again here.

Note that our bottleneck here is the second loop and our way of checking whether an element exists in a list. It takes us O(n) for each possible element. If we can eliminate this search cost, it would be really nice and we would be one step closer to the ideal solution.

Using Hashmap

As we saw in the Math Method, we were having the problem with the time cost of checking whether the difference value exists in the input array. In this approach we are going to significantly decrease the lookup cost to O(1) on average by using a hashmap as our lookup structure.

Our thought process is the same as the previous method. We are going to divide the target value into two parts (not two halves), and then for each element we assign our num1 as the current element we are on, and search whether num2 exists in the array.

Different from the Math Method, we are going to use a hashmap to store our visited elements and their corresponding indexes, and at each iteration we look up whether our num2 exists in the hashmap.

Another tricky part of this solution is that, when we look for the difference in the array, we search for it among the already visited elements rather than the whole array. And this design also avoids returning the same index twice since when we are on an element, we don't consider it twice by the design of the algorithm itself.

Our time complexity is O(n) since we iterate through the whole array. And for each iteration we have O(1) time cost of execution (hashmap lookup) on average.

Space complexity is O(n). We only use a hashmap to store our elements and indexes and it can grow up to the size of the input array in the worst case.

Overall, we reached the best possible time complexity we could get since it is a must to iterate through the whole input array. For the space complexity, we perform worse compared to brute force, which was only O(1). That's a trade-off of this solution, but since we are within the question's constraints, it's OK.

One last side note, when we store the elements and their indexes in our hashmap structure, there could be collision of key values (array's elements), and in this case we would have the problem of losing the earlier element's index, but since question guarantees us to have only one valid answer, that is our final pair of elements must be unique in the array. So we don't get any collision of this type.

Below I am going to walk you through the actual solution code.

Code Walkthrough

Here at line 2 we initialize our hashmap. I used a built-in type dict here, it is more than enough for our purpose.

We start our loop at line 3 over the range of array's length. Note that I iterate over indexes, not the elements themselves, since we are going to need the indexes as well when storing our elements to our hashmap.

At the start of the loop at line 4, we first assign our difference variable to target - nums[i].

Between lines 5–8 we have our if else block. Here, before storing the current element to the hashmap, we first check if the difference exists in the hashmap. That's because we don't want to return the same index twice as mentioned in the approach section. You can observe this behaviour explicitly with Example 3.

In the if block, if we find the difference value in the hashmap, which means we have found a pair (the current element and an element we visited before in the array) that sums up to target value, we return that pair's indexes. And also the order of the pair's indexes is not important.

Note that at the if block we check whether the value returned by .get() method is not None, that's because Python interprets 0 as a falsy statement, and it could miss the first element in the list since its index is 0.

If we don't find the difference value in the hashmap, else block, we store the current element and its index to our hashmap at line 8 for a later iteration to find.

Below you can step through the algorithm and see the intermediate steps. I encourage you to use pen and paper to slow down the process to observe more carefully what happens.

def twoSum(nums: List[int], target: int) -> List[int]:
    hashmap = {}
    for i in range(len(nums)):
        difference = target - nums[i]
        if hashmap.get(difference) is not None: ## Python interprets 0 as False in condition statements, so we check it explicitly.
            return [hashmap.get(difference), i]
        else:
            hashmap[nums[i]] = i

Conclusion

So for the conclusion we designed an efficient solution for our Two Sum problem. The problem is designed to improve your use of hashmaps. I hope it did.