TL;DR: Sort, then for each anchor run two pointers from both ends to find pairs summing to its negation. Skip duplicates in three places (anchor, left, right), only after recording a match. O(n squared).
How to approach it Frame it as a reduction: "Fix one element, then it's two-sum on the rest. With the array sorted, two-sum runs with two pointers in O(n) and, the real reason to sort, duplicates become adjacent, so uniqueness is skip-conditions instead of a set of tuples." That one-breath summary tells the interviewer you understand why each ingredient is there. Clarify: return values or indices? (Values: sorting destroys indices, and uniqueness is defined on values.)
After sorting, fix the anchor and walk two pointers inward, skipping equal neighbors so triplets stay unique:
A strong answer
def three_sum(nums: list[int]) -> list[list[int]]:
nums.sort()
n, result = len(nums), []
for i in range(n - 2):
if nums[i] > 0:
break # sorted: no zero-sum triplet can start > 0
if i > 0 and nums[i] == nums[i - 1]:
continue # skip duplicate anchors
lo, hi = i + 1, n - 1
target = -nums[i]
while lo < hi:
s = nums[lo] + nums[hi]
if s < target:
lo += 1
elif s > target:
hi -= 1
else:
result.append([nums[i], nums[lo], nums[hi]])
lo += 1
hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1 # skip duplicate seconds
while lo < hi and nums[hi] == nums[hi + 1]:
hi -= 1 # skip duplicate thirds
return result
O(n²) time, O(1) extra space beyond output. Narrate the three duplicate skips as you write them (anchor, left, right) because that's the part being graded. The nums[i] > 0 early break is a nice flourish: sorted and positive means everything after sums positive.
assert three_sum([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]]
assert three_sum([0, 0, 0, 0]) == [[0, 0, 0]] # the duplicate gauntlet
assert three_sum([1, 2, 3]) == []
assert three_sum([]) == []
assert three_sum([-2, 0, 1, 1, 2]) == [[-2, 0, 2], [-2, 1, 1]]
[0,0,0,0] is the test to run by hand: it exercises every skip condition at once.
The skip-before-recording bug from the editor note is worth demonstrating rather than trusting, so we ran it. Move the left-pointer duplicate skip to the top of the while loop, the placement that feels tidier:
while lo < hi:
if nums[lo] == nums[lo - 1]: # tempting, and wrong here
lo += 1; continue
...
On [-1, 0, 1, 2, -1, -4] this version returns only [[-1, 0, 1]] (executed): with the anchor on the first -1, the left pointer starts on the second -1, sees it equals its neighbor, and steps over it before ever testing the pair, walking straight past [-1, -1, 2]. The correct placement skips duplicates only after recording a match, because at that point the pair has been counted once and further equal values can only produce repeats. Same comparison, same line of code, two positions, one of which silently drops a third of the answer, which is why interviewers watch where you put it rather than whether you know duplicates need handling.
What interviewers probe next (1) Three-sum closest: same skeleton, track best by abs(s - target); duplicates stop mattering, and noticing that is the signal. (2) Why not a hash-set approach? It works (fix two, look up the third) but uniqueness needs normalized tuples in a set and it's the same O(n²) with worse constants; having compared them shows judgment, not memorization. (3) Four-sum / k-sum: one more outer loop per k, or the recursive k-sum reduction; sketch the recursion, don't fully implement. (4) "Sum to T, not zero?" target = T - nums[i]; flagging that your code already parameterizes cleanly takes five seconds.
Common mistakes Deduping with set(tuple(...)) after generating duplicates: accepted at some loops, but at Meta/xAI the pointer-skip version is the expected answer and the set version invites "now do it without extra memory." Skipping duplicates before recording the first match (skips valid triplets like [-1,-1,2]). Off-by-one in while lo < hi guards inside the skip loops: an index-out-of-range live is costly; the guard pattern above avoids it. And forgetting this is O(n²): claiming O(n log n) gets corrected immediately.