Leetcode - 3SUM (with JavaScript)

Today I am going to show how to solve the 3 Sum algorithm problem.

Here is the problem:

In my previous blog, I talked about the solution to the 2Sum algorithm. For this problem. we could’ve used a hash table to store every number, similar to the solution in the 2Sum algorithm. Then we could’ve done double “for” loops and checked if the current number’s complement already exists in the table. But that wouldn’t be the most efficient way to solve this problem.

Instead, I am going to solve this problem by using two pointers that will give us O(n^2) time complexity. In this approach, the first thing we need to do is to sort the given array in ascending order.

After sorting the array, we are going to iterate through it and set our two pointers. A left pointer will be set to a number that comes immediately after the current number and a right pointer will be set to the number at the end of the array. Then we are going to find our current sum which is the sum of our current number, a left number, and a right number.

Now we check if our current sum is equal to our target sum, which in this case is 0.

If it is equal, we just add those three numbers to our final array (triplets).

If the current sum is less than 0, we move the left pointer to the right by one to increase the sum. Because we earlier sorted the given array in ascending order, we know that each number is greater than the number to its left.

If the current sum is greater than 0, because we know that each number is smaller than the number to its right, we can move the right pointer to the left by one to decrease the sum.

var threeSum = function(array) {
     array.sort((a,b) => a - b);
    const triplets = [];

    for(let i=0; i < array.length - 2; i++){
        if(array[i] != array[i-1]){ // making sure our solution set does not contain duplicate triplets
            let left = i + 1;
          let right = array.length - 1;

            while (left < right){
                const currentSum = array[i] + array[left] + array[right];
                if (currentSum === 0){
                    triplets.push([array[i], array[left], array[right]]);
                    while(array[left] == array[left + 1]) left ++
                    while(array[right] == array[right - 1]) right -- // making sure our solution set does not contain duplicate triplets
                    left ++;
                    right --;
                } else if(currentSum < 0) {
                    left ++
                } else if(currentSum > 0){
                    right --
                }
            }
        }
    }
    return triplets
};