The tell: Triples summing to zero, with duplicates in the input and no duplicate triples in the output.
How you get there
1Sort first — that enables both the two-pointer inner scan and the duplicate skipping.
2Fix each element, then run the sorted two-pointer search on the remainder.
3Skip repeated values at every level, or the same triple is emitted many times.
Solution
Python
def three_sum(nums: list[int]) -> list[list[int]]:
nums.sort()
out: list[list[int]] = []
for i, x in enumerate(nums):
if x > 0:
break # sorted: no zero sum possible beyond here
if i > 0 and x == nums[i - 1]:
continue # skip duplicate anchors
lo, hi = i + 1, len(nums) - 1
while lo < hi:
total = x + nums[lo] + nums[hi]
if total < 0:
lo += 1
elif total > 0:
hi -= 1
else:
out.append([x, nums[lo], nums[hi]])
lo += 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1 # skip duplicate seconds
return out
Time
O(n²)
Space
O(1) excluding the sort and output
What goes wrong
De-duplicating by pushing results into a set works but wastes the O(n²) enumeration on repeats.