Find all unique triplets in an array that sum to zero (3Sum).

How to think about it

Recognise the pattern

3Sum is two-sum upgraded by one dimension. The moment you see “triplets that sum to X,” think: fix one element, then reduce to two-sum on the rest. The two-sum subproblem uses two pointers (so you need the array sorted first). This fix-one-then-two-pointer pattern generalises to k-sum problems.

Build the approach step by step

Brute force is three nested loops: O(n³), plus a set to deduplicate. Passable for n≈100, but the interview expects better.

Reduction to two-sum:

1. Sort the array. O(n log n) — dominates nothing in this problem.
2. For each index i, you want two numbers in nums[i+1:] that sum to -nums[i] (the “needed sum”).
3. Run a two-pointer search (left=i+1, right=n-1) on that slice.
4. Skip duplicates at the outer loop: if nums[i] == nums[i-1], this fixed element produces the same triplets — skip.
5. Skip duplicates at the inner pointers: after recording a match, advance both pointers past any repeated values before continuing.

Why does sorting enable step 5? Because equal values cluster together, so a single while nums[left] == nums[left+1]: left += 1 sweep is sufficient.

Complexity

• Time — O(n²): sorting is O(n log n); the outer loop runs n times and each two-pointer pass is O(n), giving O(n²) overall.
• Space — O(1) extra (ignoring the output list). In-place sort.

The trap and the early-exit optimisation