Three Sum (LeetCode #15)
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 Three Sum problem, you’re in the right spot.
This is a question in 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 interviews.
It’s okay if this one has been giving you a hard time. Let’s get right into it so you can get your solution. 🙌🏻
Initial Setup 🏗
The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see Polya’s Problem Solving Techniques):
- We’ll be given an integer list of
nums - The
numslist is be length0 <= nums <= 3000 - The integers in
numswill be-10^5 <= nums[i] <= 10^5 - We must find all triplets where
num1 + num2 + num3 == 0 - The triplets must not contain any duplicates triplets
- We cannot reuse numbers
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.
We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.
I think that’s enough for us to get started! Let’s do it.
Variable and Initial Loop Setup 🦾
It turns out this is really similar to the Two Sum problem that we’ve previously worked on. We’re only extending it slightly.
The optimal solution for this is also a quadratic (e.g. O(n^2)) solution, so don’t worry if you had trouble finding a way to solve this. There is no O(n) time complexity solution for this problem that I know of. It be like that in life sometimes.
Consequently, we’re going to need to use two loops on this one (one nested inside the other).
The first thing we want to do is set up our baseline variables that we’ll use throughout the rest of the problem:
The first thing we’re doing here is setting up a results variable with a set that we’ll use to house our triplet answers as we find them. We’re using a set since it will automatically prevent us from ending up with duplicates!
The next thing we’re doing is sorting our nums list. While this runs in a time complexity of O(n log n) time, it’s okay because our final answer is going to be O(n^2) anyways.
We need our nums list to be sorted because of how we’re about to do our next step — running our loops. 🙌🏻
Inner Loop Setup 🔁
The key to this problem is the idea that we’re going to iterate over every number in our nums sorted list and do a two-pointer technique search over the remaining numbers in a second loop (if that sounded confusing, don’t worry — we’ll get into it).
The first thing we need to do is write out our initial for loop and set up our pointers:
Notice that left always starts as whatever i is (in our initial for loop) but with 1 added to it.
The next thing we’re doing is to write a while loop that totals up the current numbers in nums at i, left, and right. Triplets. See how this is coming together already?
This gives us the current total of these three numbers, exactly what we need to tell if we’ve found a good triplet!
Now that we have this total, we just need to check if total is 0. If it is, we should add this triplet to the results variable we initialized with a set:
Nice, right?
Now we’ve come to the magic piece of the puzzle. For every triplet of numbers, we want to decrease the right pointer if the total we’ve found is greater than 0. This is because we’ve sorted the nums. If the total is greater than 0, this means that our largest number (with the right pointer) needs to decrease, right?
For all other times (if total is less than 0 or if we’ve found a total that equals 0 but need to increase the pointers to avoid an infinite loop), we can add 1 to our left pointer.
This is what this looks like in code form:
As you can see, the last thing we needed to do was to return the results.
There you go — the final answer to this problem is right above. This solution runs in O(n^2) time complexity with O(n) space complexity (due to storing a variable of the sorted nums).
Conclusion
Nice job on making it through this one! 🔥 I hope the explanation helped you out.
Keep an eye out for the rest of these Blind 75 coding challenges articles from me. I’m going to be solving them and publishing as I go.
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 (I really, really like book recommendations).
Thanks for reading!
Nathan
(GitHub, LinkedIn, Twitter, and Personal Site)
