3Sum

The problem

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

• i, j, k are distinct indices
• nums[i] + nums[j] + nums[k] === 0

Order of triplets (and order inside a triplet) usually does not matter; the set of triplets must be unique.

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

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

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

Two Sum’s big sibling. Pattern: sort → fix one index → two pointers on the rest, with careful deduping.

Brute force

Three nested loops, push every zero-sum triple, then unique with a set of sorted strings. O(n³) time, messy uniqueness. Mention and discard for n up to a few hundred interview-scale.

function threeSumBrute(nums: number[]): number[][] {
  const n = nums.length;
  const set = new Set<string>();
  const out: number[][] = [];

  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 t = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);
          const key = t.join(",");
          if (!set.has(key)) {
            set.add(key);
            out.push(t);
          }
        }
      }
    }
  }
  return out;
}

Time	O(n³) + set overhead
Space	O(n) for the set of answers

Optimal: sort + two pointers

1. Sort ascending.
2. For each i from 0 to n - 3:
   • Skip duplicate nums[i] (same as previous).
   • Optional prune: if nums[i] > 0, break (remaining sums positive).
   • lo = i + 1, hi = n - 1.
   • While lo < hi:
     • sum = nums[i] + nums[lo] + nums[hi]
     • If sum === 0 → record; move lo/hi and skip duplicates
     • If sum < 0 → lo++
     • If sum > 0 → hi--

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

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

    let lo = i + 1;
    let hi = n - 1;

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

  return res;
}

Time	O(n²) after O(n log n) sort
Space	O(1) or O(n) depending on sort; answer space separate

Why sort first?

• Two pointers need order.
• Duplicates become adjacent — skip with while instead of a global set of triples.

Hash-set per fixed i (alternate)

For each i, run Two Sum with a set on the suffix. Still O(n²), but deduping is easier after sort + skip-i, or with a set of triple keys. Interviewers usually prefer two pointers for 3Sum.

Edge cases

• Fewer than 3 elements → []
• All zeros → one triple [0,0,0]
• No solution → []
• Many duplicates — skip logic is the real test
• Negatives and positives mixed — sort handles ordering

Common bugs

• Skipping duplicates only on i but not on lo/hi after a hit
• Using nums[lo] === nums[lo + 1] before moving (off-by-one)
• Mutating indices incorrectly so lo crosses hi
• Returning index triples instead of values (wrong problem)

Follow-ups

1. 3Sum Closest — track best sum vs target
2. 4Sum — fix two indices + two pointers → O(n³)
3. 3Sum Smaller — count pairs under a bound
4. Two Sum / Two Sum II — building blocks

Interview delivery

1. Restate uniqueness + zero target.
2. Brute O(n³) → sort + two pointers O(n²).
3. Call out dedupe as the hard part.
4. Code; dry-run [-1,0,1,2,-1,-4].
5. Complexities.

Related

• Two Sum
• Container With Most Water
• Valid Palindrome — two pointers flavor
• Merge Intervals — sort-then-scan family

Further reading

• LeetCode 15 — 3Sum