Overview

Given an integer array nums, return all the unique triplets [nums[a], nums[b], nums[c]] such that a, b, and c are distinct indices and nums[a] + nums[b] + nums[c] === 0.

The solution set must not contain duplicate triplets. Return triplets sorted in ascending order, and the list of triplets sorted lexicographically.

Implement threeSum(nums).

Constraints

• 3 ≤ nums.length ≤ 3000
• -100000 ≤ nums[i] ≤ 100000
• No duplicate triplets in the output.
• Aim for $O(n^2)$ time.

Examples

threeSum([-1, 0, 1, 2, -1, -4]);
// → [[-1, -1, 2], [-1, 0, 1]]

threeSum([0, 1, 1]);
// → []  — no triplet sums to 0

threeSum([0, 0, 0]);
// → [[0, 0, 0]]

Notes

• Sort the array first. Fix one element and use two pointers on the remaining subarray to find pairs that sum to its negation.
• Skip duplicates at every level to avoid repeating triplets.
• Early termination: if the fixed element is positive, no further triplets can sum to 0.

Solution

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

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

    let lo = i + 1, hi = nums.length - 1;
    while (lo < hi) {
      const sum = nums[i] + nums[lo] + nums[hi];
      if (sum < 0) lo++;
      else if (sum > 0) hi--;
      else {
        result.push([nums[i], nums[lo], nums[hi]]);
        while (lo < hi && nums[lo] === nums[lo + 1]) lo++;
        while (lo < hi && nums[hi] === nums[hi - 1]) hi--;
        lo++;
        hi--;
      }
    }
  }

  return result;
}

Resources

• 3Sum — LeetCode
• Two-pointer technique — Wikipedia