DSA 3Sum

The problem

3Sum finds every triplet of values at three different positions that adds to zero. Each distinct triplet is reported once. A list with no working triplet answers with an empty list.

Triplets are printed in sorted order inside, and the list of triplets follows the order of the sorted input. That fixed order keeps the printed answer the same on every run.

cases = [
    ([-1, 0, 1, 2, -1, -4], [[-1, -1, 2], [-1, 0, 1]]),
    ([-2, 0, 0, 2, 2], [[-2, 0, 2]]),
    ([0, 0, 0], [[0, 0, 0]]),
    ([1, 2, 3], []),
    ([], []),
]
for nums, expected in cases:
    print("nums", nums, "->", expected)

The first case holds two triplets. The second case holds one triplet built from repeated values. The last two cases hold none.

Intuition: try every triple, and drown in repeats

A first idea tests every group of three positions. Some group either sums to zero or does not. The idea always finds the true triplets.

Two traps wait inside it. The count of triples grows fast as the list grows. Repeated values also produce the same triplet again and again, once per matching group of positions.

nums = sorted([-2, 0, 0, 2, 2])
found = []
triples = 0
for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        for k in range(j + 1, len(nums)):
            triples += 1
            if nums[i] + nums[j] + nums[k] == 0:
                found.append([nums[i], nums[j], nums[k]])
print("triples tested:", triples)
print("zero-sum finds:", found)

Five values hold ten triples. The single triplet of values appears four times in the finds, because either 0 and either 2 can take part. The values repeat, and the raw search cannot tell the copies apart.

Brute force: every triple, with duplicates removed

The brute force sorts the list first. Three nested loops then test every group of three positions in order. A set of tuples keeps each distinct triplet once.

def three_sum_brute(nums):
    nums = sorted(nums)
    seen = set()
    tested = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            for k in range(j + 1, len(nums)):
                tested += 1
                if nums[i] + nums[j] + nums[k] == 0:
                    seen.add((nums[i], nums[j], nums[k]))
    return [list(t) for t in sorted(seen)], tested

result, tested = three_sum_brute([-1, 0, 1, 2, -1, -4])
print("triplets:", result)
print("triples tested:", tested)
result, tested = three_sum_brute([-2, 0, 0, 2, 2])
print("triplets:", result)
print("triples tested:", tested)

The set repairs the repeat problem. The cost problem stays. A list of twenty values holds over a thousand triples, and every one is tested even after the answers are already found.

The optimal solution: fix one value, hunt the pair with two pointers

Fixing one value turns the rest into a two-sum hunt on the sorted remainder. Two pointers start at the ends of the remainder and close in. A sum below zero moves the left pointer up, and a sum above zero moves the right pointer down.

Sorting groups equal values together, so duplicates sit side by side. A fixed value equal to the previous fixed value is skipped whole. Its triplets were already found by the earlier copy.

def three_sum(nums):
    nums = sorted(nums)
    triplets = []
    skips = 0
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            skips += 1
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                triplets.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    skips += 1
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    skips += 1
                    right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return triplets, skips

cases = [
    ([-1, 0, 1, 2, -1, -4], [[-1, -1, 2], [-1, 0, 1]]),
    ([-2, 0, 0, 2, 2], [[-2, 0, 2]]),
    ([0, 0, 0], [[0, 0, 0]]),
    ([1, 2, 3], []),
    ([], []),
]
for nums, expected in cases:
    result, skips = three_sum(nums)
    print("nums", nums, "->", result, "match:", result == expected, "skips:", skips)

All five cases pass. The skip counts show the duplicate rules firing. No triplet appears twice, because every repeat is passed over by rule instead of filtered afterwards.

Walkthrough: the hunt with the fixed value at -1

The walk sorts the main case first. The fixed value is the second value in the sorted list. The pointers then close in on zero.

nums = sorted([-1, 0, 1, 2, -1, -4])
print("sorted:", nums)
i = 1
left, right = i + 1, len(nums) - 1
while left < right:
    total = nums[i] + nums[left] + nums[right]
    print("fixed", nums[i], "+ left", nums[left], "+ right", nums[right], "=", total)
    if total == 0:
        print("triplet found:", [nums[i], nums[left], nums[right]])
        break
    if total < 0:
        left += 1
    else:
        right -= 1

The very first sum already lands on zero. The triplet is -1, -1, and 2, built from the fixed value and the second copy of -1 beside it. One fixed value needs only this single inward walk, and here the walk ends at its first step.

Complexity

The brute force tests every triple of positions, so its time is O(n^3) for n values. The pointer solution runs one linear hunt per fixed value, so its time is O(n^2) after an O(n log n) sort.

The pointer solution stores only the answer triplets and a few indexes, so its extra space is O(1) beyond the sorted copy and the answer. The brute force also stores its set of found triplets.

for n in [5, 10, 20]:
    triples = n * (n - 1) * (n - 2) // 6
    hunts = n * n
    print("values", n, "- brute triples:", triples, " pointer steps up to:", hunts)

At twenty values the brute force tests 1140 triples. The pointer hunts reach at most 400 steps. Sorting pays a small price once and buys the whole gap.

Edge cases and pitfalls

Fewer than three values can hold no triplet. Four zeros hold exactly one distinct triplet, not four. Skipping repeats after a find is what keeps that answer at one.

def three_sum(nums):
    nums = sorted(nums)
    triplets = []
    skips = 0
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            skips += 1
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                triplets.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    skips += 1
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    skips += 1
                    right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return triplets, skips

print("empty:", three_sum([]))
print("two values:", three_sum([0, 0]))
print("four zeros:", three_sum([0, 0, 0, 0]))
print("no triplet:", three_sum([1, 2, 3]))
print("all negative:", three_sum([-5, -2, -1]))
print("pair uses one position twice check:", three_sum([0, 1, -1]))

The last case sums to zero with three distinct positions. A search that reused one position could also fake answers from a single value and its double. Three separate indexes rule that error out by construction.

Forgetting the skip after a find is the classic duplicate bug. The pointers move past equal values on both sides before the hunt resumes. Each side needs its own skip loop.