Solving the 3Sum Problem

The "3Sum" problem is a classic algorithmic challenge that requires finding all unique triplets in an array that add up to zero. This problem steps up from the simpler "Two Sum" problem and tests your ability to manipulate arrays and apply the two-pointer technique.

The Problem

Given an array nums of integers, the task is to find all unique triplets in the array that sum up to zero.

The Solution

Here's a JavaScript function that effectively solves the 3Sum problem:

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

  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    let left = i + 1,
      right = nums.length - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];

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

The Explanation

• Sort the Array: The array is sorted to use the two-pointer technique effectively.
• Iterate and Find Triplets: Loop through the array, for each element, use a left and right pointer to find triplets.
• Skip Duplicates: Skip over duplicate elements to avoid repeating triplets.
• Two-Pointer Technique: Adjust the left and right pointers to find different combinations that sum up to zero.

Conclusion

This problem is a perfect example of the application of sorting and two-pointer techniques in solving complex array problems. It's often used in coding interviews to assess a candidate's problem-solving and array manipulation skills.