3Sum

3Sum is one of the most asked medium problems, and it is two lessons in one. The first is a reduction: a three-value problem becomes n separate two-value problems, each solved with the converging template from Two Sum II. The second is duplicate handling, which is where most candidates lose the problem — not in the idea, but in returning the same triplet twice.

The problem

Given a list of integers, return every distinct triplet of values [a, b, c] taken from three different positions such that a + b + c = 0. Each triplet should appear once, whatever the order of its values; the order of the triplets does not matter.

• [3, -2, 1, 0, -1, -2, 1] → [[-2, -1, 3], [-2, 1, 1], [-1, 0, 1]]. The value -2 appears twice in the input, but [-2, -1, 3] is listed once.
• [0, 0, 0, 0] → [[0, 0, 0]].
• [1, 2, 3] → [].

Constraints: 3 ≤ len(numbers) ≤ 3,000; values between -10⁵ and 10⁵.

Clarifying questions

• Distinct by values or by positions? By values: [-2, -1, 3] using the first -2 and the same triplet using the second -2 count once.
• Can I reorder or modify the input? Assume yes. If not, sort a copy and say it costs O(n) memory.
• Does the order of the output matter? No.
• Can the same position be used twice? No — [0] alone does not make [0, 0, 0].

Approach 1: the simple way

Try every triple of positions; store each matching triplet sorted in a set to drop repeats.

1def three_sum_brute(numbers: list[int]) -> list[list[int]]:2    """Every triple of positions; a set removes repeated triplets."""3    n = len(numbers)4    found: set[tuple[int, int, int]] = set()5    for i in range(n):6        for j in range(i + 1, n):7            for k in range(j + 1, n):8                if numbers[i] + numbers[j] + numbers[k] == 0:9                    found.add(tuple(sorted((numbers[i], numbers[j], numbers[k]))))10    return [list(t) for t in sorted(found)]

Time O(n³), space O(t) for the t triplets found. At n = 3,000 there are about 4.5 × 10⁹ triples — far over budget. An O(n²) solution is about 4.5 × 10⁶ steps, which is what the constraint invites.

The key insight

Fix the first value, numbers[i]. The problem is now: find two values after it that add up to -numbers[i]. That is exactly Two Sum II — and it runs in O(n) if the array is sorted. So sort once, then for each i run converging pointers on the part to its right. n pair searches of O(n) each gives O(n²).

Sorting also solves the duplicates, because equal values end up next to each other. Two skips are enough:

• Skip a repeated first value. If numbers[i] == numbers[i - 1], every triplet starting with this value was already found in the previous round. Skip it.
• Skip a repeated second value after a match. After recording a triplet, move left past any copies of the value just used. Otherwise the next round pairs the same value with the same partner and records the triplet again.

Once numbers[i] and numbers[left] are fixed, the third value is determined, so these two skips are enough to prevent repeats.

One more free win from sorting: if numbers[i] > 0, everything after it is positive too, so no triplet can sum to zero. Stop.

Approach 2: sort, fix one, two pointers on the rest

1def three_sum(numbers: list[int]) -> list[list[int]]:2    """Return every distinct triplet of values that adds up to zero."""3    numbers.sort()4    triplets: list[list[int]] = []5    n = len(numbers)6    for i in range(n - 2):7        if numbers[i] > 0:8            break                              # all later values are positive too9        if i > 0 and numbers[i] == numbers[i - 1]:10            continue                           # skip 1: same first value as before11        left, right = i + 1, n - 112        while left < right:13            total = numbers[i] + numbers[left] + numbers[right]14            if total < 0:15                left += 116            elif total > 0:17                right -= 118            else:19                triplets.append([numbers[i], numbers[left], numbers[right]])20                left += 121                right -= 122                while left < right and numbers[left] == numbers[left - 1]:23                    left += 1                  # skip 2: same second value as before24    return triplets

Dry run on [3, -2, 1, 0, -1, -2, 1], which sorts to [-2, -2, -1, 0, 1, 1, 3] (positions 0 to 6):

Three triplets, each once. The row for i = 1 is the first skip at work: without it, the second -2 would search the same range and find [-2, 1, 1] again. To see the second skip at work, run [-2, 0, 0, 2, 2]: after recording [-2, 0, 2], left lands on the second 0, and without the skip the loop records [-2, 0, 2] a second time.

Complexity. Sorting is O(n log n). The outer loop runs up to n times, and each inner search moves its pointers at most n times in total, so O(n²) time, which dominates the sort. Space is O(1) beyond the output for the pointers — but be honest about the sort: Python's list.sort works in place yet may use up to about n / 2 slots of temporary memory, so the worst case is O(n).

Approach 3: a hash set per first value

Fix i as before, then scan the rest keeping a set of values seen; if -(numbers[i] + numbers[j]) is in the set, you have a triplet. It is also O(n²) time but needs O(n) extra space and still needs sorting or a set of tuples to remove repeats. Mention it — it is what you would use if the follow-up bans reordering the input — but the sorted two-pointer version is the expected answer.

Edge cases

• All zeros, such as [0, 0, 0, 0]. First round records [0, 0, 0]; skip 2 moves past the other zeros; later rounds are skipped by skip 1. Output [[0, 0, 0]].
• All positive or all negative. No triplet; the early break or the pointer loop ends quickly and returns [].
• Exactly three elements. One outer round, one comparison.
• Many copies of each value. The skips keep the output free of repeats however many copies there are.

We checked all three approaches against each other on 300 random lists of up to 10 values between −6 and 6. The narrow range forces many repeated values, which is exactly where 3Sum code breaks.

Follow-ups

• "3Sum Closest: the triplet whose sum is nearest a target." Same loops; track the best abs(total - target), and no duplicate skipping is needed because you return one number.
• "4Sum." Add one more fixed index outside, with its own duplicate skip: O(n³). In general, k-sum is O(n^(k−1)) by fixing k − 2 values.
• "Count the triplets with sum less than a target." When total < target, every right' between left + 1 and right also works, so add right - left and move left.