3Sum

Examples

Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]

These are the only two distinct sets of three values from the list that sum to zero.

Input: nums = [0, 1, 1]
Output: []

No three numbers here add up to zero.

Input: nums = [0, 0, 0]
Output: [[0, 0, 0]]

The only triplet available happens to sum to zero.

Constraints

• 3 <= nums.length <= 3000

• -10^5 <= nums[i] <= 10^5

Approach

A direct approach is to check every possible group of three numbers and keep the ones that sum to zero, using a set to avoid reporting duplicates — but that looks at every triplet, which is a lot of wasted comparisons.

A much better approach: first sort the array. Then, for each number (treating it as the "first" number of a triplet), use two pointers on the rest of the sorted array — one starting right after it, one at the very end — to find a pair that, together with the fixed number, sums to zero. Because the array is sorted, you know exactly which pointer to move if the running total is too big or too small, and duplicate values sit right next to each other, so they're easy to skip.

Solutions

Brute Force — Check Every Triplet

Look at every possible group of three numbers, and whenever one sums to zero, record it (using a canonical, sorted form of the triplet as a key so duplicates aren't reported twice).

function threeSum(nums) {
  const result = [];
  const seen = new Set();
  const n = nums.length;

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      for (let k = j + 1; k < n; k++) {
        if (nums[i] + nums[j] + nums[k] === 0) {
          const triplet = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);
          const key = triplet.join(",");
          if (!seen.has(key)) {
            seen.add(key);
            result.push(triplet);
          }
        }
      }
    }
  }

  return result;
}

Time: O(n³) · Space: O(n) for the results and de-duplication set

Optimal — Sort + Two Pointers

Sort the array first. Then fix each number in turn as the first element of a triplet, and use two pointers on the remainder of the array to find a pair summing to its negative. Skip over duplicate values at every level so no triplet is reported twice.

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

  for (let i = 0; i < n - 2; i++) {
    if (nums[i] > 0) break; // smallest remaining number is positive, no way to reach zero
    if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicate "first" numbers

    let left = i + 1;
    let right = n - 1;

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

  return result;
}

Time: O(n²) · Space: O(log n) to O(n), depending on the sort's internal space (not counting the output)