How do you find all unique triplets in an array that sum to zero?
Sort the array, fix one number, and use two pointers on the rest to find pairs that cancel it. Skip equal values to avoid duplicate triplets. It runs in O(n squared).
Explain it simply
Sorting turns a hard search into a guided one. Fix the first number, then you need two numbers that add up to its negative. With a sorted array you put one pointer at the left and one at the right: if the sum is too small move the left pointer up, if too large move the right pointer down.
The tricky part is duplicates. After using a value, skip over any equal neighbours so the same triplet is not listed twice.
Example
function threeSum(nums) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
let l = i + 1;
let r = nums.length - 1;
while (l < r) {
const sum = nums[i] + nums[l] + nums[r];
if (sum < 0) l++;
else if (sum > 0) r--;
else {
result.push([nums[i], nums[l], nums[r]]);
l++;
r--;
while (l < r && nums[l] === nums[l - 1]) l++;
}
}
}
return result;
}
console.log(JSON.stringify(threeSum([-1, 0, 1, 2, -1, -4]))); // Output: [[-1,-1,2],[-1,0,1]]Complexity
Time O(n squared) (the sort is O(n log n)), space O(1) beyond the output.
What to say in the interview
"I sort the array, loop over each value as the first element, and run two pointers on the remainder. Sum too small moves the left pointer, too large moves the right. I skip repeated values for the first element and after each hit. Time is O(n squared) and extra space is O(1) apart from the output."
Common mistakes
- Not skipping duplicates, so the same triplet appears twice.
- Using a hash set of triplets instead of sorting; it works but is heavier.