Sorting the array is the whole trick, and the reason isn’t speed. Sorting puts equal values next to each other, which is what lets you skip duplicate triplets without ever building a set. Candidates who miss that end up writing a correct solution wrapped in a canonicalize-and-hash contraption, and the interviewer quietly marks them down for it.
The problem itself is one line. Given an integer array nums, return every unique triplet [a, b, c] where a + b + c == 0. LeetCode calls it problem 15. It shows up in loops at Google, Amazon, Meta, Bloomberg, Goldman Sachs and Citadel, usually in the first coding round, and usually with about twenty-five minutes on the clock. The triplet-finding is not the hard part. The uniqueness requirement is.
The brute force you should spend twenty seconds on
Three nested loops, check every combination, dump the hits into a set of sorted tuples so the duplicates collapse. O(n³). Say it out loud, state the complexity, then say you can do better and start moving. The point of naming it isn’t to show you can write it. It’s to establish the number you’re about to beat, so that when you say “O(n²)” thirty seconds later the interviewer knows you understand what you bought.
What you should not do is spend five minutes coding it. Some interviewers will let you. That’s a patience test and you can fail it.
Why the Two Sum reflex costs you here
Most people arrive at this problem straight from Two Sum, so the reflex is to reach for a hash map. Fix one element a, then hunt the rest of the array for a pair summing to -a, using the same seen-set trick. That genuinely works, and it genuinely runs in O(n²).
It also produces [-1, 0, 1] and [0, 1, -1] and [1, -1, 0] as three separate answers. To collapse them you sort each triplet, hash it, and keep a result set, which costs you O(n) extra space in the inner pass plus however large the output set grows. You’ve traded the clean thing for a bookkeeping thing. Worse, from the interviewer’s seat it reads as pattern matching: you recognized “sum problem,” fired the hash map, and never asked what structure the problem actually has.
The structure it has is that once the array is sorted, the sum of a fixed element and a pair is monotonic in the pair’s positions. That’s the property worth finding.
Sorting buys adjacency, and adjacency buys dedup
Sort the array. Walk a pointer i through it. For each i, you now need two values from the suffix that sum to -nums[i], and because the suffix is sorted you can find them with two pointers converging from both ends. If the running total is too small, the only way to grow it is to move the left pointer right. Too large, move the right pointer left. Every step eliminates a value permanently, so the inner search is O(n).
def three_sum(nums):
nums.sort()
n, out = len(nums), []
for i in range(n - 2):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
lo, hi = i + 1, n - 1
while lo < hi:
total = nums[i] + nums[lo] + nums[hi]
if total < 0:
lo += 1
elif total > 0:
hi -= 1
else:
out.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo + 1]:
lo += 1
while lo < hi and nums[hi] == nums[hi - 1]:
hi -= 1
lo += 1
hi -= 1
return outO(n) outer, O(n) inner, so O(n²) overall. The O(n log n) sort vanishes underneath it. Same shape as Container With Most Water, with an extra loop wrapped around it.
The if nums[i] > 0: break is worth writing even though it changes nothing asymptotically. On a sorted array, if the smallest of your three values is already positive, no triplet from here forward can reach zero. On arrays that skew positive it cuts real work, and interviewers notice when a candidate prunes without being asked.
The three places duplicates crawl back in
Skipping duplicates is where this problem is actually graded, and there are exactly three spots.
The first is the outer loop. If nums[i] equals nums[i-1], every triplet starting at i was already found at i-1, so skip. Note the comparison points backwards. Writing if nums[i] == nums[i + 1]: continue looks equivalent and is a real bug: on [-1, -1, 2] it skips the first -1, which was the one that mattered, and you lose the triplet entirely. People write this version under time pressure more often than you’d guess.
The second and third are the two inner pointers, and they only fire after you’ve recorded a hit. Advance lo past any run of equal values, pull hi back past its own run. Both inner loops leave the pointers sitting on the last copy of each run, which is why the lo += 1 and hi -= 1 after them are load-bearing rather than redundant.
Trace [-1, 0, 1, 2, -1, -4], which sorts to [-4, -1, -1, 0, 1, 2]. At i = 0 you need a pair summing to 4 out of [-1, -1, 0, 1, 2], and the largest available pair is 3, so nothing. At i = 1 you need 1: the ends give -1 + 2, recording [-1, -1, 2], then the skips move you to 0 + 1, recording [-1, 0, 1], then the pointers cross. At i = 2 the value is -1 again, so the outer skip fires and you never re-derive those two. At i = 3 you need 0 from [1, 2] and the pointers cross immediately. Both triplets fall out in order, without a result set or a cleanup pass.
| Approach to 3Sum (all unique triplets summing to zero; n = length of input array) | Time | Extra space beyond the output | How duplicates are removed | Verdict in an interview |
|---|---|---|---|---|
| Three nested loops over all index combinations | O(n³) | O(number of triplets found) | Sort each triplet, insert into a hash set | State it as a baseline, do not code it |
| Fix one element, hash-map Two Sum over the remaining suffix | O(n²) average, O(n³) adversarial hashing worst case | O(n) for the seen-set, plus the result set | Canonicalize every triplet, dedupe at the end | Accepted, but reads as pattern matching |
| Sort, then converge two pointers over the suffix for each fixed element | O(n²) | O(1), ignoring the sort’s own overhead | Skip runs of equal values in three places | The expected answer |
| Sort, then binary search for the third value for each pair | O(n² log n) | O(1) | Same adjacency skips as two pointers | Correct, strictly slower, no reason to pick it |
What gets asked right after you finish
Space complexity is the first trap. Answering “O(1)” flatly invites a push, because the sort has its own cost: Python’s Timsort uses O(n) auxiliary space, and Java’s Arrays.sort on primitives is a dual-pivot quicksort with O(log n) stack. The clean answer is “O(1) beyond the output and whatever the sort allocates,” and if you’re allowed to destroy the input, say that too, since sorting in place is the reason you get O(1) at all.
Then comes “can you beat O(n²)?” The answer is no, not in any way you’d ship. 3SUM was conjectured for decades to require quadratic time and is still used as the base for conditional hardness proofs across computational geometry. Grønlund and Pettie broke the barrier in 2014 with a deterministic algorithm shaving off a sublogarithmic factor, and nobody implements it. Saying “there’s a 3SUM-hardness literature, the best known bound is barely subquadratic, and it isn’t practical” is a much stronger answer than guessing at some O(n log n) approach that doesn’t exist.
Two variations show up often enough to prepare for. If the interviewer asks for original indices rather than values, sorting destroys them, so you pair each value with its index before sorting, or you fall back to the hash approach. And if the target becomes an arbitrary k instead of zero, almost everything survives except the nums[i] > 0 prune, which is only valid because zero is the target. Deleting that line unprompted when the target changes is the sort of detail that separates a strong hire signal from a fine one.
The family this problem belongs to
Nailing the duplicate skips here pays off across a cluster of near-identical questions:
- “Find the triplet whose sum is closest to a target” (3Sum Closest, LeetCode 16) uses the same skeleton but tracks the minimum absolute difference, and needs no dedup at all because you’re returning one number.
- “Count triplets with sum strictly less than a target” (3Sum Smaller, 259) exploits sortedness harder: when the total is under target, every pair between
loandhialso works, so you addhi - loand advance once. - “Same thing, four numbers” (4Sum, 18) adds another outer loop for O(n³), and in Java or C++ the running sum needs to be a 64-bit type or it overflows on the standard test cases.
- “Generalize to k numbers” collapses into recursion that peels off outer loops until it bottoms out at the two-pointer 2Sum, giving O(n^(k-1)).
The two-pointer convergence itself is the same machinery behind Trapping Rain Water, so the real unit of study is one movement rule with four reasons to apply it, rather than four separate problems.
If you rehearse one part of this, rehearse typing the three duplicate skips from memory, correctly, the first time, without a compile-and-fix cycle. Everything else in 3Sum is a two-pointer loop you already know. That block is the part the interviewer is actually watching you write.
Drill the patterns next:
