Three Sum

Problem

Given an integer array nums, return all the unique triplets [nums[i], nums[j], nums[k]] such that:

• i != j
• i != k
• j != k
• nums[i] + nums[j] + nums[k] === 0

The solution set must not contain duplicate triplets.

Mind Map

• Sort the array first.
• Fix one number and search for the remaining two values.
• Use two pointers:
  • Left pointer moves forward.
  • Right pointer moves backward.
• If the total is too small, move left.
• If the total is too large, move right.
• Skip duplicate values to avoid repeated triplets.

Brute Force Approach

Check every possible combination of three numbers and store only unique triplets whose sum is equal to 0.

function threeSum(nums: number[]): number[][] {
  const result: number[][] = [];
  const seen = new Set<string>();

  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      for (let k = j + 1; k < nums.length; 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;
}