3Sum: Finding Zero-Sum Triplets
The Prompt
Given an integer array `nums`, return all the triplets `[nums[i], nums[j], nums[k]]` such that `i != j`, `i != k`, and `j != k`, and `nums[i] + nums[j] + nums[k] == 0`. Notice that the solution set must not contain duplicate triplets.
Understanding the Problem
Find every distinct triplet summing to zero. Three nested loops cost O(n³) and still leave you deduplicating triplets by hand — the two hard parts of this problem are the cubic blowup and the "no duplicate triplets" rule, and both fall to the same move: sort first.
After sorting, fix one element nums[i] as the anchor; the task collapses to finding two later elements summing to −nums[i]. On a sorted range that inner search is the classic two-pointer sweep, and sorting also parks equal values side by side, making duplicates trivial to skip.
The Interview Flow
Interviewer
Given an array of integers, find all unique triplets that sum to zero.
Candidate
This sounds like an extension of the Two Sum problem. A brute-force approach with three nested loops would be O(n^3), which is too slow. I need to avoid duplicate triplets as well.
Interviewer
Correct. How can you optimize it?
Candidate
To handle duplicates easily and to use a more efficient approach, I should first sort the array. This will take O(n log n). After sorting, I can iterate through the array with a primary pointer, let's say `i`.
Interviewer
And for each element at `i`, what do you do?
Candidate
For each `nums[i]`, the problem reduces to finding two numbers in the rest of the array that sum to `-nums[i]`. This is the Two Sum problem on a sorted subarray. I can use the two-pointer technique for this part. I'll set a `left` pointer to `i+1` and a `right` pointer to the end of the array.
Interviewer
How do you handle duplicates with this approach?
Candidate
Since the array is sorted, duplicates will be adjacent. When I iterate with `i`, if the current element is the same as the previous one, I can just skip it. Similarly, when I find a valid triplet with the `left` and `right` pointers, I add it to my result, and then I must move both pointers inward, skipping any subsequent duplicate values to avoid adding the same triplet again.
Interviewer
That is a comprehensive and optimal approach. The overall time complexity would be O(n^2) due to the nested loop structure after the initial sort. Please go ahead and code it.
Why do sorting plus two pointers cover every triplet?
With left and right at the ends of the range after i, the sum moves predictably: too small (s < 0) means only a larger left value can help, so move left inward; too big (s > 0) means move right inward. Each step permanently discards pairs that provably cannot sum to the target, so the sweep is O(n) per anchor and O(n²) overall — every candidate pair is either examined or safely eliminated.
Duplicate handling rides on sortedness: skip an anchor equal to its predecessor, and after recording a hit, advance left past equal values. Any repeat triplet would have to reuse the same value pattern, which these skips make impossible. Time is O(n²) with O(1) extra space beyond sorting and the output — better than hash-based variants that pay memory for the same bound.
O(n^2) Solution with Sorting and Two Pointers
- First, sort the input array `nums`. This is crucial for the two-pointer approach and for handling duplicates.
- Initialize an empty list to store the resulting triplets.
- Iterate through the array with a for loop from index `i = 0` to `n-2`.
- Inside the loop, to avoid duplicate triplets, add a check: if `i > 0` and `nums[i] == nums[i-1]`, then `continue` to the next iteration.
- For each `i`, initialize two pointers: `left = i + 1` and `right = n - 1`.
- Start a while loop that runs as long as `left < right`.
- Calculate the sum `s = nums[i] + nums[left] + nums[right]`.
- If `s < 0`, we need a larger sum, so increment `left`.
- If `s > 0`, we need a smaller sum, so decrement `right`.
- If `s == 0`, we found a triplet. Add `[nums[i], nums[left], nums[right]]` to the result list. Then, to avoid duplicates, increment `left` and decrement `right`. Also, add inner while loops to skip over any duplicate values at the new `left` and `right` positions.
- After the loops complete, return the list of triplets.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
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 left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
left++;
right--;
while (left < right && nums[left] === nums[left - 1]) left++;
while (left < right && nums[right] === nums[right + 1]) right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}Explanation
Solve nums = [−1, 0, 1, 2, −1, −4], which sorts to [−4, −1, −1, 0, 1, 2].
1Anchor i = 0 (−4): s = −4 + (−1) + 2 = −3 < 0, so move L right. Every later L gives s = −4 + 0 + 2 = −2 or −4 + 1 + 2 = −1 — still negative, so the −4 anchor yields nothing.
2Anchor i = 1 (−1): s = −1 + (−1) + 2 = 0 — record [−1, −1, 2]. Move both pointers inward, skipping values equal to the ones just used.
3Same anchor: s = −1 + 0 + 1 = 0 — record [−1, 0, 1]. Now L and R cross, ending this sweep.
4Anchor i = 2 is −1 again — equal to nums[1], so skip it to avoid duplicate triplets. Later anchors (0, 1, 2) are all ≥ 0, so no new triplet can sum to zero. Answer: [[−1, −1, 2], [−1, 0, 1]].
Complexity Analysis
TIME
O(n^2)
SPACE
O(1) or O(n)
Finished working through this one?
Mark it complete to track it on your Data Structures path.