DEV Community

Urfan Guliyev
Urfan Guliyev

Posted on

9 1

Leetcode - 3SUM (with JavaScript)

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

Here is the problem:
Alt Text

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
};


Enter fullscreen mode Exit fullscreen mode

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Engage with a sea of insights in this enlightening article, highly esteemed within the encouraging DEV Community. Programmers of every skill level are invited to participate and enrich our shared knowledge.

A simple "thank you" can uplift someone's spirits. Express your appreciation in the comments section!

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found this useful? A brief thank you to the author can mean a lot.

Okay