In our previous lesson we looked at to some sorted, which I think is a hard problem because you need some divine intuition in order to solve it. However, I think once you've seen the solution it's pretty easy to remember. Now, today's problem known as threesome is something that actually depends upon that for its optimal solution. So it's definitely harder. However, I actually got tested for this when I interviewed at Google, so this is not something that you want to skip. And in this tutorial we will look at the problem statement, it's nice solution as well as its optimal solution. So let's go. Here's the threesome problem statement. You will be provided with the number array

and our objective is to return triplets such that they add up to the value of zero. There are two additional conditions. One is that we cannot reuse members at the same index. As an example, if one of the values is zero, we cannot just return 0, 0 0 because we will be reusing the zero member. The second additional condition is that the solution set must not contain duplicate triplets. For example, if our input contains multiple threes, multiple zeros and multiple minus threes, we can only return the triplet minus three zero and three once.

Now as always, if you're not provided any examples, it's good to come up with a few of your own. This particular problem does come with this example and you can see that we have triplets minus one, minus one two that add up to zero and the triplet minus 1 0 1, that adds up to zero. Now we can flesh out the function definition so that we know the kind of inputs and the outputs that we are dealing with. We are dealing with the number array and we will be returning an array of couples. Each couple will contain three numbers and within the function body we have our result initialized and that is what we will return. And our objective is to fill this up with as many doubles

that add up to the value zero. Now let's think through the simplest solution that we can come up with. We are looking for sets of threes within the input array such that they add up to zero and we can find all sets of threes with the simple triple loop. So let's code that up. We loop through the input array three times and terminate at minus two and minus one for INJ so that we have values to use for J and K, which we initialize at I plus one and J plus one. This ensures that at any given point I, J and K do not overlap and they're not equal to each other,

which was one of our requirements. And within the core of the triple loop, we checked that the sum of numbers i, J and K is equal to zero. And if it is, we add that to our result array. Now at this point you might think that we have a correct solution, however, there is actually one more requirement that is the solution set must not contain duplicates and we haven't done anything for that right now and we can actually see that play out with a simple example that contains multiple duplicate answers. And if we run this you can see that it pretty much blows up. Now there are lots of ways to solve this,

but the key realization over here is that the time complexity of the algorithm right now is cubic because of those triple loops, which means that we can sort the input array in and log in without affecting this time complexity. And this will greatly help us in finding these duplicates. We first create a copy of the input NUMs with NUMs dot slice and then sort them by using a custom comparer function. Now this custom comparer function A minus B is actually required if you want to sort numbers and I have a lesson dedicated to that within the video description. Now with the input number sorted, it's pretty easy to check if the current number is a

duplicate of the previous one. The only word of caution over here is that we can only do it in the second iteration of the loop because the first iteration there is no previous number to look at, which means for I we make sure that it is greater than zero. For J, we make sure that it is greater than I plus one. And for K it is greater than j plus one. Other than that, we simply check if the current value is the same as the previous value and if so, we continue on to the next iteration of that particular loop. And now with these changes in place, if we run a code again, you can see that we only get one answer and this is actually a correct implementation

of the problem statement. Well, the question is can we make this solution perform better than cubic time? And the answer is yes. The optimal solution is actually in quadratic time. So let's look at how we can achieve that. The key realization over here is that once we have the first number and the remainder of the array is already sorted, we are essentially dealing with a twosome sorted problem. Now I do have a lesson dedicated to that particular problem that I believe in the video description, but let's look at how we can implement that over here. Consider this particular input array which we already have sorted.

Now at the point when I is looking at minus 20, the remainder of the array is essentially a twosome sorted problem where we want to find something that as up to the target value of 20 so that it cancels out the minus 20 to give us a threesome of zero. And the smart solution to that particular problem is using two pointers and looping through the remainder of the array. Only once we maintain a left pointer initialized to the first element and a right pointer initialized to the last element, and then we sum these two numbers. And if they are two big, for example, they are in this case 'cause the sum is 23, we decrement the right pointer

and then do the same check again. And this time the value is too small. So we increment the left pointer to increase the value and this time the sum is a perfect 20 and we have found our solution. So let's look at how we can implement this in code. And in my opinion, understanding the mechanics of this problem is hard. However, writing the code is actually easy once you understand those mechanics. As you mentioned, we initialized the left to the first element, which is I plus one in this case and the right to the last element, which is numbs length minus one.

And then we loop as long as left is smaller than right, that is we haven't run out of elements. We calculate the sum of NUMs I left and right and if they are less than zero, the value is too small, we increment left. If it is greater than zero than the value is too big, we decrement right? Otherwise the sum is zero, which is just perfect. So we add the nus, I left and right into our solution set and this is almost a complete solution. One final thing that we have to remove Duplicates, duplicates of I are already being filtered out.

So let's look at what we need to do for duplicates of left and right. We only care about duplicates when we actually find a solution because that is the case when duplicates will actually end up in our solution when the values are not right, they're going to be skipped over multiple times and that will be fine. And that is actually a key observation. We only need to skip over the duplicate of left or right and its corresponding pair will automatically get skipped because it'll never be the right value. Let's look at an example. We have eye pointing at minus two and left and right pointing to solution points which are

surrounded by duplicates. If we successfully skip over the duplicates of left, then the duplicates of right will never be the right answer anyways and they will get skipped by the other conditions in our wide loop. And with this observation in place, we can code up the skipping portion of our twosome problem. We increment left and then we make sure that the new left is not the same as the previous left. And if it is the same, then we increment left to jump to the next value. And if you're going to be incrementing left in this loop, we also need to make sure that left has not become equal to right and this is the entire

optimal solution for the threesome problem. It has time complexity of O of N squared because there is one loop going through I and a second loop, which is incrementing left and right for the remainder of the array. And the O of N log N provided by sort will collapse into this O of N squared as well.