Run it
The two-pointer version against brute force with both operation counts, and the deduplication removed so you can see the duplicate triples it produces.
Sort, then fix one and two-pointer the rest
O(n²) time — an outer loop with an inner linear scan — and O(1) extra space beyond the output, or O(n) if the sort is counted.
The structure is worth naming: reduce three-sum to n instances of two-sum on a sorted array. Fixing nums[i] turns "find three summing to zero" into "find two summing to -nums[i]", which two pointers solve in O(n).
The duplicate handling, which is the whole difficulty
Three separate skips are needed, and each addresses a different source of repeats.
Duplicate first elements. if i and nums[i] == nums[i-1]: continue. Without it, [-1, -1, 0, 1] produces [-1, 0, 1] twice — once for each -1.
Duplicate second elements. After recording a triplet, advance lo past any repeats. Without it, [-2, 0, 0, 2, 2] produces [-2, 0, 2] several times.
The third element needs no separate skip: with the first two fixed, the third is determined, so no additional duplicate can arise.
The alternative — collecting into a set of sorted tuples — also works and costs O(n) extra space and hides the reasoning. Interviewers generally want the skip version, because it demonstrates understanding of where the duplicates come from.
The if nums[i] > 0: break line is a genuine optimisation rather than a correctness fix: once the smallest of the three is positive, no triplet can reach zero, so the rest of the loop is wasted.
Reducing the third loop
The brute force is three nested loops, O(n³). Fix the first element and the problem becomes "find two numbers summing to -values[i]" — which is Two Sum, and on sorted input Two Sum is two pointers in O(n).
n iterations of an O(n) inner scan is O(n²), and the sort is O(n log n) so it disappears into that. Using a hash map for the inner search is also O(n²), and then deduplication is much harder — which is the argument for sorting.
Deduplication is the real difficulty
Two places need it. Skip a fixed element equal to the previous one, or every triple starting with that value is emitted twice. And after recording a triple, advance past any repeats of both pointer values, or the same triple is found again inside the same scan.
Sorting is what makes both a simple adjacency check. Without it you would collect triples into a set of sorted tuples — correct, and it allocates for every candidate.
The early exits worth mentioning
Once values[i] > 0 the smallest possible triple is already positive, so the scan can stop entirely. That is not a complexity improvement and it is a large constant on real input.
The generalisation is kSum: fix an element and recurse down to the two-pointer base case, giving O(n^(k−1)). Naming that shows you see the pattern rather than the single problem.
Tracing the duplicates
[-1, 0, 1, 2, -1, -4] sorted becomes [-4, -1, -1, 0, 1, 2].
| i | nums[i] | Window | Result |
|---|
| 0 | −4 | lo=1, hi=5 | No triplet sums to 0 |
| 1 | −1 | lo=2, hi=5 | -1 + -1 + 2 = 0 → record; then -1 + 0 + 1 = 0 → record |
| 2 | −1 | — | Skipped — same as nums[1] |
| 3 | 0 | lo=4, hi=5 | 0 + 1 + 2 = 3 > 0, hi falls to 4, loop ends |
Two triplets, no repeats. The skip at i = 2 is what prevents [-1, 0, 1] appearing twice.
Walking that table aloud is a good way to demonstrate the solution in an interview, because it exercises exactly the case the duplicate handling exists for.
Edge cases
| Case | Result |
|---|
| Fewer than 3 elements | [] |
All zeros, [0,0,0] | [[0,0,0]] — one triplet |
All zeros, [0,0,0,0] | [[0,0,0]] — still one, thanks to the skips |
| All positive | [] — caught by the early break |
| All negative | [] |
| No triplet sums to zero | [] |
| Many duplicates | Each distinct triplet once |
The [0,0,0,0] case is the cleanest test of the duplicate logic, and worth mentioning unprompted.
The generalisation to k-sum
The structure extends: fix k−2 elements with nested loops, and two-pointer the last two.
| Problem | Approach | Complexity |
|---|
| Two-sum, sorted | Two pointers | O(n) |
| Two-sum, unsorted | Hash map | O(n) |
| Three-sum | One loop + two pointers | O(n²) |
| Four-sum | Two loops + two pointers | O(n³) |
| k-sum | k−2 loops + two pointers | O(n^(k−1)) |
Four-sum has a better alternative worth knowing: hash all pairwise sums, then look for two pairs summing to the target — O(n²) time and O(n²) space, better than O(n³) when memory allows. That trade appears again in the "meet in the middle" technique for subset problems.
The variants
Three-sum closest. Find the triplet whose sum is nearest a target. Same structure, and instead of comparing against zero, track the smallest absolute difference. No duplicate handling needed, because only one answer is returned.
Three-sum smaller. Count triplets with sum below a target. When nums[i] + nums[lo] + nums[hi] < target, every position between lo and hi also works — so add hi - lo and advance lo. That counting shortcut is the insight, and it keeps the whole thing O(n²).
Three-sum with multiplicity. Count the number of index triplets rather than distinct value triplets — a counting problem over value frequencies, with careful case analysis for repeated values.
Two-sum with a target other than zero. Trivially the same code with the comparison adjusted.
What it is testing
Do you sort first? Sorting enables the two-pointer reduction, and it is the move that turns O(n³) into O(n²).
Do you handle duplicates correctly? This is the actual assessment. Producing correct triplets with repeats is a fail.
Do you see the reduction to two-sum? Saying "fix one element and this becomes two-sum on the rest" is the answer the interviewer is listening for.
Do you state complexity precisely? O(n²), with the sort's O(n log n) absorbed.
Do you find the early exit? Breaking when the smallest element is positive is a small demonstration of attention.
The transferable lesson is reduction: recognising that a harder problem is a loop around an easier one you already know. That habit applies far beyond this question.
Recap in one screen
- Sort, fix one element, and two-pointer the remainder — three-sum is n instances of two-sum.
- O(n²) time, O(1) extra space beyond the output.
- Skip duplicate first elements at the outer loop, and duplicate second elements after recording a triplet.
- The third element needs no skip, because the first two determine it.
- The pattern generalises: k−2 loops plus two pointers, at O(n^(k−1)).