How to Solve Two Sum - Solving Leetcode Problems #1

Let's kickstart this series with the infamous Two Sum🚀

If you want to try to solve this question first, here is the link

Table of Contents:

• The Question
• Brute Force Solution
• Optimizing Our Solution
• Optimized Solution Code
• Time Complexity
• Conclusion

---

The Question

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Brute Force Solution

Your initial approach to this question will probably be to use two for loops and go over every item, comparing each item to the rest of the array. So let's see what that looks like:

def twoSum(nums, target):
    for i in range(len(nums))-1:
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

Because you don't want to ever compare items at the same index, you have to offset the first for loop to stop one short, and the second for loop to start one index after the outer for loop, but this one will go to the end each time.

This code does indeed work but after submitting it to Leetcode, you may notice that it is extremely inefficient

In fact, this approach has a time complexity of O(n^2) which is not very good, because as we get more and more items, the time our algorithms take run will grow much larger.

How can you improve this? Let's go find out.

Optimizing Our Solution

When in doubt, use a hash table(dictionary). This may be the best advice you can get when trying to solve these types of questions, because of how fast hash tables can operate. If you are trying to optimize your algorithms, hash tables should be one of the first things you think of.

How does a hash table help us? Well first we need to understand something important, and that is taking the complement of a number.

So let's use the first example in the question above, and that is having a target of 9, and the two elements are 2 and 7 at indexes 0 and 1 respectively.

Say we are at index 0 and have the element 2, instead of using addition to find our answer why not use subtraction. If you subtract 9-2 you will notice we get 7... Wait a minute! That's the number we are looking for.

Okay now that you understand the subtraction process, let's incorporate a hashtable. If we start with an empty python dictionary, then you might be wondering how we are going to get 7 when we are at 2.

Well here's the fun part, we aren't. 🤨

Let me explain, by continuing through, now imagine that have put 2 as the key and 0(index) as the value for our dictionary, now we have one that looks like this cache={2: 0}.

Okay so now as we move forward to index 1, we get the value 7 right. Now you can do the subtraction 9-7 and what do we get? Well, 2 and guess what, we have 2 in our dictionary! So all we have to do is return the value at 2 and our current index and we have our answer. Let's see how this looks in code

Optimized Solution Code

def twoSum(nums, target):
    cache = {}
    for i in range(len(nums)):
        compliment = target - nums[i]
        if compliment in cache:
            return [cache[compiment], i]
        cache[nums[i]] = i

Time Complexity

Now let's press that submit button and see what happens!

Whoa! that is so much faster than our first approach. And that is because our solution is now running in O(n) time, meaning that the time our algorithm takes to run will grow proportional to the size of the nums array, and not grow much larger.

---

Conclusion

Two Sum is one of those problems with a very obvious brute force solution, but to optimize it you need a little trick, and in our case, that was using subtraction and a hash table.

Thank you for reading this article! I hope this solution has helped you work through this problem and helped develop your understanding of data structures and algorithms.

Have an amazing day!