Let's do 3 Sum with JavaScript

This problem is similar to the “Two Sum” problem, and how can we come up with an efficient solution just by making a small modification. After that, we will also give you a try of the code so that you can understand it well. So let’s get started.

First of all, let’s make sure that we understand the problem statement correctly. In this problem, we have given an array of integers, and we have to find out all the unique triplets such that their sum is equal to 0, and there is one more condition: we cannot choose the same index twice. It simply means that if we have chosen an index, we cannot use it again to find the total sum of 0.

So given all of these conditions, we have to find out all of the possible triplets. Let us look at our sample test cases. In our first test case [-1, 0, 1, 2, -1, -4], right now, what are some of the triplets that, when summed, will give us the total sum of 0. First of all, I can find a triplet of -1, -1, and 2. If we add all of them, we will get the sum 0, and similarly, we can get one more triplet that will be 0, 1, and -1. In this particular array, we have two unique triplets by which we can form the total sum as 0. right? So for this particular test case, these two triplets will be our answer.

In our next test case, we have [0, 1, 1], so this is the only triplet, and if we sum all of these elements, the sum will not be 0, right? So for this particular test case, an empty array will be the answer.

Now let us look at our third test case. we can see that once again we have an array [0, 0, 0], and all of its elements are zero. Now we know that it says that these elements cannot be duplicated, but if we notice, we are not duplicating the indices. correct? Only the element is duplicated, so even if two elements have the same value and they are at different indices, we can pick them, so one such triplet that can be formed will be 0 0, and 0, and if we add them all up, we get the total sum of 0.

So for this particular test, only this triplet will be answered.

I want to let you know that this problem is based on a similar problem, “Two Sum,” where we have given an array and have to find out two integers whose sum equals a target value. I want you to take a recap and realize what we did wrong with our original and what we did right. We spotted this array correctly, and as soon as we sort it, we get our array something like [-4, -1, -1, 0, 1, 2] and let us have to find out two values that sum up and give our target value of -3.

So what was the approach over here? We sorted the array, and then what did we do?

We took two pointers first in the beginning, and then at the very end, we summed both of these values, so my current sum will be -4 plus 2 and that is -2. Now since this target value is smaller than my sum, that means we have to pick a smaller number, and how did we pick a smaller number? We moved our right pointer one space backward, and that is how we will try to get the sum as -4 plus 1, and that will be -3 for our pair.

So just try to keep this in mind, and based upon this, we will build an efficient solution to our actual problem.

So once again, we have a sample array, and what did we do? First of all, we sorted it as soon as we found the array, and the array will look something like this: [-4, -1, -1, 0, 1, 2], and now we have to convert this problem to the two-sum problem.

So here is something that we can do. What we can do is pick our first element to be -4, so out of the triplet we get one value or we fix one value so that one of our values will be minus four, and we make a condition so that one of my values is -4, and what if the array that I’m remaining with is this entire array [-1, -1, 0, 1, 2]. right?

Now notice what our problem has reduced to: using this array, we can once again take a left pointer and a right pointer. correct? and we have one value that is fixed for now. Instead of finding the triplets, we have to find that pair plus this fixed value, and our total sum should be 0.

So we will apply the same approach as ours to some questions, and what we’re going to do is take the minor 4 value and then try to find a triplet such that when I add these three values, my total sum should be 0.

Just wait for a little while, and all of this will start making sense.

For this particular condition, when we choose our first value as -4, we will not find a triplet, so this part is done. Now try to understand that we took care of all the triplets that could start with -4 right now. we have to move ahead, so what do we do this time? we are going to choose -1 as our fixed value. That is the value at the first index, so we fix our value to -1, and then what is the array that I’m remaining with? We are remaining with only [-1, 0, 1, 2]. So we have an array over here.

So once again, our problem changes. Now the fixed value is -1, and once again, we will take two pointers left and right, and then we will try to come up with a pair plus this -1, and the sum should be 0.

This should give us some triplets, so we have a value of -1, and then what can we do? we can try to find a triplet of -1 and 2 that will be 0, and then if we move ahead, we will find one more triplet of -1 plus 0 and then 1. that is once again equal to 0. So I found two triplets, and one added gives us the sum as 0, which is correct.

I hope it has started to make a little bit of sense, so let us keep moving ahead.

This time I’m done with this -1 again, and if we see we have one more -1 for this time, I’m going to fix this value as my constant value. What is the array [0, 1, 2] that I’m remaining with? I am remaining with 0 1 and 2. So once again, my problem reduces to 0, 1, and 2, and I will take a left pointer and a right pointer, this is my fixed value, so once again, I will try to find a pair along with the sixth value and try to get the total reward of 0. This time I will get one more triplet, which is -1 plus 0 plus 1, and that is equal to 0. Just keep moving ahead now, so now I will fix my next value, which is 0, so I fix it, and what are the remaining values 1 and 2? So this is the new use case that I have to work with, and if we realize this, it will once again not give me any triplets. So while going through all of this, how many triplets did we find? we found this, this, and this, so there are three triplets. Since the problem asks for unique triplets, we can add all of these triplets to a function. All the duplicate values will just go away, and we cannot have duplicate elements left with our answer, and these will be our unique triplets.

const threeSum = function (nums) {
 const target = 0;
 nums = nums.sort((a, b) => a - b);
 let output = [];

 for (let i = 0; i < nums.length; i++) {
  let start = i + 1;
  let end = nums.length - 1;

  while (start < end) {
   let sum = nums[i] + nums[start] + nums[end];
   if (sum == target) {
    output.push([nums[i], nums[start], nums[end]]);
    start++;
    end--;
   } else if (sum < target) {
    start++;
   } else {
    end--;
   }
  }
 }

 // remove duplicate arrays
 const uniqueArrays = new Set(output.map(JSON.stringify));
 const result = Array.from(uniqueArrays, JSON.parse);
 return result;
};

let nums = [-1, 0, 1, 2, -1, -4];
console.log(threeSum(nums));

In conclusion, the problem at hand is to find unique triplets in an array such that their sum equals zero, with the constraint of not using the same index twice. To approach this efficiently, we draw parallels with the “Two Sum” problem, sorting the array and fixing one element at a time to transform the problem into finding pairs that sum up to a target value. By iteratively fixing elements and applying the two-pointer technique on the remaining array, we can identify unique triplets that satisfy the given conditions.

The key insight is to break down the problem into smaller subproblems, where each fixed element reduces the problem to finding pairs in the remaining array. This approach helps us avoid duplicate triplets and efficiently navigate through the array to identify all valid solutions.

By following this method and carefully handling edge cases, such as arrays with identical elements at different indices, we can find and accumulate unique triplets that meet the criteria. The final step involves ensuring uniqueness by eliminating duplicate triplets before presenting the solution.

Overall, this strategy optimizes the solution to the problem, providing a clear and systematic approach to finding unique triplets with a sum of zero in a given array.

And Finally,

Please don’t hesitate to point out any mistakes in my writing and any errors in my logic.

I’m appreciative that you read my piece.