Two Sum (LeetCode #1)

Image by Hamish Duncan on Unsplash

This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include Building Your Own Bitcoin Node and Maximum Product Subarray.

Introduction

If you’re looking for a quick walkthrough of an optimal solution to the LeetCode Two Sum problem, you’re in the right place.

This is a question from the Blind 75 LeetCode code challenge list, a group of questions put together by a tech lead at Facebook that’s been touted as a great way to prep for coding challenge-style interviews.

Don’t beat yourself up if you’re here because it gave you a hard time. We’re all learners in this industry at different points along the path.

I don’t want to waste any more time, so let’s get started!

Initial Setup 🏗

The first thing we should always do is understand the problem (see: Polya’s Problem Solving Techniques). According to the rules, it says that:

1. We’ll have a list of nums
2. We’ll be given a target number, and we must find two numbers in the nums list that add up to it
3. We should find the two numbers in nums that add up to target and return the indices where they occur in the list
4. We can assume that every input will have one solution
5. We cannot use the same instance of a number twice (e.g. nums = [2, 9] and target = 4 will not allow us to reuse the same number 2twice to make 4)

This is enough for us to get started. 🔥

I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.

I also won’t be talking through “less optimal” solutions. You came here for an answer, right? You’re going to get a good one.

Let’s get to it.

Building Our Variables and Loop 🔁

While we could use two nested loops to search our list of nums for two values that add up to target, that would give us a time complexity of O(n^2) which isn’t the best we can figure out together.

If you already wrote something like that, you might have even noticed that it didn’t pass all the test cases on LeetCode. Such is life.

Instead, we can initialize a dictionary that will allow us to keep track of values we’ve already seen (which is a very common pattern that you can use on other problems in the future, btw).

We can store this dictionary right inside our function. At this point, this is what it should look like:

The next thing we should do is to initialize a new for loop to iterate over each of our numbers in the nums list. It should look something like this:

Nice. Now that we have each number and a tracking dictionary to use, we get to the heart of this problem — the ability to look backwards in time.

Let’s Look Backwards ⏳

As it turns out, we can store every number we’ve already seen by putting it into the tracking dictionary with a value of the index we saw it at.

Then, for each number in the nums list, we can check to see the difference between it and the target value and then check to see if that difference already exists in the tracker dictionary.

If it does, we know that we’ve officially found two numbers that equal the target.

In order for this process to be useful, we should store every number as a key in the tracker list with the value as the index where it was found:

We’ll also use enumerate for our loop which allows us to get both the index and number for each spot in the nums list.

The end result for this (and the actual end solution for the entire problem) looks like this:

While LeetCode doesn’t require us to return an empty array if we don’t find a solution (since the rules of the problem state that we’ll always have one), I think it’s a good idea to do it anyways. Its cleaner code and provides a fallback just in case.

This final algorithm will run in O(n) time complexity with O(n) space complexity (for storing each value in the tracker dictionary).

Conclusion

There you go. 👏🏻

I hope you learned something as much as I enjoyed writing this.

Keep an eye out for the rest of these Blind 75 coding challenges articles. It’s going to be a fun ride.

Also, feel free to reach out to me on any of the links below if you want to talk about coding, cool tech, or anything else (like book recommendations).

Thanks for reading. 🔥

Nathan

(GitHub, LinkedIn, Twitter, and Personal Site)