Solving the Three Sum Problem in JavaScript

The Three Sum problem is a classic coding challenge that often appears in technical interviews. It involves finding all unique triplets in an array of numbers that add up to a target sum. In this blog post, we'll explore how to solve this problem in JavaScript.

The Problem Statement

Given an array of integers, we need to find all unique triplets that sum up to a target value. If such triplets exist, we should return them in an array. If no triplets can be found, we return an empty array.

Example

Let's consider an example to understand the problem:

const nums = [-1, 0, 1, 2, -1, -4];
const target = 0;

// Expected output: [ [-1, -1, 2], [-1, 0, 1] ]

In this example, there are two unique triplets that sum up to the target value of 0.

Approach

To solve the Three Sum problem, we can use a combination of sorting the array and employing a two-pointer technique. Here are the steps to solve the problem:

1. Sort the input array in ascending order. Sorting helps to eliminate duplicates and allows us to use a two-pointer approach efficiently.

2. Initialize an empty result array to store the triplets that sum up to the target.

3. Iterate through the sorted array, fixing one element as a potential candidate for the first number of the triplet. For each element at index i, we'll use two pointers, left and right, to find the other two numbers in the triplet.

4. Inside the loop, calculate the sum of the current element, the left pointer element, and the right pointer element.

   • If the sum is equal to the target value, we have found a valid triplet, so we add it to the result array.

   • If the sum is less than the target, we increment the left pointer to move towards a larger value.

   • If the sum is greater than the target, we decrement the right pointer to move towards a smaller value.

5. While iterating through the array, we need to avoid duplicates. If the current element is the same as the previous one, we can skip it to avoid duplicate triplets.

6. Continue this process until all unique triplets have been found.

7. Return the result array containing all unique triplets.

Let's implement this approach in JavaScript.

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

  for (let i = 0; i < nums.length - 2; i++) {
    if (i === 0 || (i > 0 and nums[i] !== nums[i - 1])) {
      let left = i + 1;
      let right = nums.length - 1;
      const sum = target - nums[i];

      while (left < right) {
        if (nums[left] + nums[right] === sum) {
          result.push([nums[i], nums[left], nums[right]);
          while (left < right and nums[left] === nums[left + 1]) left++;
          while (left < right and nums[right] === nums[right - 1]) right--;
          left++;
          right--;
        } else if (nums[left] + nums[right] < sum) {
          left++;
        } else {
          right--;
        }
      }
    }
  }
  return result;
}

const nums = [-1, 0, 1, 2, -1, -4];
const target = 0;

const result = threeSum(nums, target);
console.log(result); // Output: [ [-1, -1, 2], [-1, 0, 1] ]

In this implementation, we use two loops to iterate through the array efficiently and find all unique triplets that sum up to the target value.

Conclusion

The Three Sum problem is a common coding challenge that tests your ability to work with arrays, sorting, and a two-pointer technique. By following the approach outlined in this blog post and implementing it in JavaScript, you can efficiently find all unique triplets that meet the specified condition. This problem is not only a great exercise for improving your problem-solving skills but also a useful algorithm for various real-world applications.