A solution to LeetCode Problem 15. 3 Sum in JavaScript

If you’re preparing for technical interviews or want to improve your coding skills, solving practice problems on LeetCode is a great way.

In this post, we’ll discuss a solution to the “3 sum” problem on LeetCode.

Problem Statement:

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

2 <= nums.length <= 105
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Solution

One solution to this problem is to use a brute force approach, where we consider every possible combination of three elements and check if their sum is zero. However, this solution has a time complexity of O(n^3), which is not efficient for large inputs.

A better solution is to use a two-pointer approach. We can sort the array first, and then for each element a in the array, we can use two pointers b and c to find the other two elements that sum to -a. We can move the pointers b and c towards each other to find the other two elements.

Here is the solution :

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

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

    let b = i + 1;
    let c = n - 1;
    while (b < c) {
      if (nums[i] + nums[b] + nums[c] === 0) {
        result.push([nums[i], nums[b], nums[c]]);
        b++;
        c--;
        while (b < c && nums[b] === nums[b - 1]) b++;
        while (b < c && nums[c] === nums[c + 1]) c--;
      } else if (nums[i] + nums[b] + nums[c] > 0) {
        c--;
      } else {
        b++;
      }
    }
  }

  return result;
}
 