Two Sum (LeetCode #1)
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.
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:
- We’ll have a list of
- We’ll be given a
targetnumber, and we must find two numbers in the
numslist that add up to it
- We should find the two numbers in
numsthat add up to
targetand return the indices where they occur in the list
- We can assume that every input will have one solution
- We cannot use the same instance of a number twice (e.g.
nums = [2, 9]and
target = 4will not allow us to reuse the same number
2twice to make
This is enough for us to get started. 🔥
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
If it does, we know that we’ve officially found two numbers that equal the
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
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
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. 🔥