As I stated yesterday, this problem becomes much easier to solve if you have already studied it. I don’t like those kinds of problems, but they are asked very frequently in your interviews. So make sure you practice the skills mentioned in your interviews frequently.
Problem
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]]
such that i != j
, i != k
, and j != k
, and nums[i] + nums[j] + nums[k] == 0
.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Example 2:
Input: nums = []
Output: []
Example 3:
Input: nums = [0]
Output: []
You can test your solution here
[FREE SUBS]To buy the solution for this problem, use any of the following links. The price is 3 USD. Once you send the payment, message me on IG, LinkedIn, Twitter, or by Email:
Venmo: https://account.venmo.com/u/FNU-Devansh
Paypal: paypal.me/ISeeThings
Or you can sign up for a Free Trial Below. Only 15 days left in this offer -
Step 1: Building out the Skeleton.
As always, step 1 is figuring out the deets of the problem. There are two aspects of the problem that we build on-
i,j,k refer to the indices. We can’t use values at the same times multiple times in the same triplet.
Triplets can’t have identical values throughout. For example for list [0,0,0,0], we will only return one triplet. Example 1 is an example of this.
In your interviews, your interviewer might not give you such descriptive test cases. This is a good thing. Perfect time for a question. Clarify what a “duplicate triplet” means. Even if you get these test cases, confirm the details with them.
Our analysis of the inputs and outputs gives us something to latch onto. Remember, solving these problems is like unraveling a thread. You have to attack one small area, and build it up from there. This question gives us a clear target. Namely, how do we figure out whether a triplet is a duplicate to another in our list?
Step 2- Duplicate Mechanisms
In a question like this, we can infer one thing- we will be doing a lot of lookups. Anytime we hit up a possible triplet that meets our sum requirement, we will need to check if we have already got another identical configuration. This sounds like something we can use a set for. And I did actually come up with a solution using sets, with much better space complexity.
However, I will not be covering that way here. That is because that doesn’t take advantage of some of the constraints of this question. If you are interested, just DM me using my links and I will share that solution with you. All my links are shared with you. If there is enough interest, I can just cover that as a separate post.
Instead, let’s go back to the drawing board. We have some special properties given to us, that make this problem solvable without the use of sets. These properties are the reason why the sort-multiple pointers pattern is applicable in this question. Understanding these properties will help you identify when this approach will lead to a solution. Obviously, this pattern is crucial to your interviews, so ignore the theory at your peril.
What are these properties that we absolutely must know?
Notice that we are dealing with numbers. Numbers have a few interesting properties.
Imagine we have 3 numbers a,b,c that summed to n. Replacing c with numbers larger than c will increase the value of the sum. Values lesser than c will drop the sum.
Given a sum, and 2 values, there is only one valid third value that can be part of the equation sum= val1+ val2 + val3
I haven’t said anything too revolutionary here. But take some time to really sit with these observations. Because these are the properties behind the “sort the list, then use pointers” idea that is so common in interviews. Just as a tangent, keep in mind that the pointers can work in many ways. Binary Search, 2 Sum on Sorted List, 3Sum Variants, and even 4 Sum have different pointer traversals. The idea stays the same, however.
Back to our problem, we see something wrt to the properties discussed. And these will help us create the final solution. We know that based on our current sum, we can try either lower or higher values in our triplets. It depends on whether our current sum is greater than or lower than 0.
Step 3- Sorting the input
I could have skipped the whole discussion, and directly jumped into this step. If you search for the solutions online, you will see that they do this. At most, they will point you to Two Sum II - Input Array Is Sorted and just say we will do the same process. Things would be much easier if I did that. So why didn’t I?
It’s not because I’m a masochist. I promise.
Simply put, the approach of sorting the input shows up in a lot of questions. Many of them are not directly related to the 2-Sum family of questions. Knowing when to sort will make or break your solutions. If you have to take only one thing away from this post, let it be this-
In cases where our input obeys the properties discussed earlier, AND we want to filter out solutions based on the those properties, we should sort our input.
Since I’m drinking chocolate milk as I type this, I will henceforth refer to this as the Chocolate Milk Rule. Btw since you, my dear reader, makes it possible for me to buy Chocolate Milk, I very very love you <3.
Next time you come across a Leetcode problem that uses input sorting, look at the input. You will see this to be true. Conversely, when you see a problem that obeys the Chocolate Milk Rule, sort away.
We’re actually very close to the end. Now we will use the sorted array to find all good triplets. There are a few intelligent tricks we can use to really boost our run-time.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.