Find all unique triplets in an array that sum to zero (3Sum).

How to think about it

3Sum is two-sum wearing one extra dimension, and the interviewer wants to see you collapse it back. The instant you hear “triplets that sum to zero,” the move is to fix one element and reduce the rest to a two-sum search. But the real thing being graded is not the reduction — it is whether you keep the result unique without a deduplication set bolted on afterward. Sloppy duplicate handling is where most candidates lose this one.

Sort the array first; that one step unlocks everything. Now for each index i, you are hunting two numbers in the slice to its right that sum to -nums[i], and because the slice is sorted you can sweep it with two pointers in a single pass. Sorting also clusters equal values together, which is what makes deduplication cheap: skip a fixed element when it equals its predecessor, and after recording a match, slide both pointers past any repeats before moving on. One more gift from the sort — once nums[i] turns positive, every triplet from here on is strictly positive, so you can stop early.

A worked example

def three_sum(nums):
    nums.sort()                                  # sorting unlocks two pointers + cheap dedup
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:     # skip duplicate FIXED element
            continue
        if nums[i] > 0:                          # smallest term positive -> no zero sum left
            break
        left, right = i + 1, len(nums) - 1
        target = -nums[i]
        while left < right:
            s = nums[left] + nums[right]
            if s == target:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:   # skip dup on left
                    left += 1
                while left < right and nums[right] == nums[right - 1]: # skip dup on right
                    right -= 1
                left += 1
                right -= 1
            elif s < target:
                left += 1
            else:
                right -= 1
    return result

print(three_sum([-1, 0, 1, 2, -1, -4]))
print(three_sum([0, 0, 0, 0]))
print(three_sum([1, 2, 3]))

[[-1, -1, 2], [-1, 0, 1]]
[[0, 0, 0]]
[]

The first input contains two -1s, yet the answer lists [-1, -1, 2] once, not twice — the inner skip-loops swallowed the redundant pointer positions. [0, 0, 0, 0] is the harder dedup case: four zeros could spray out many copies of [0, 0, 0], but the outer nums[i] == nums[i-1] guard fires after the first triplet and collapses them to one. And [1, 2, 3] returns [] because the early break triggers immediately — the smallest element is already positive, so no triplet can reach zero.