037. Three Sum to Zero

Why this mechanism works

Fix the smallest value of a triple in a sorted copy, then solve a two-sum problem in the suffix. Skipping repeated fixed values prevents repeating entire searches. After a match, skip equal values on both moving frontiers so the same value triple is not emitted again.

State and boundaries

i selects the first value; left and right search indices strictly after i. output contains distinct triples from completed searches.

Protocol

1. Sort a copy.
2. Skip duplicate fixed values.
3. Run inward two pointers for target -values[i].
4. On a match append the triple and advance past equal endpoint runs.
5. Move one frontier according to the sum otherwise.

Visualization

fixed -1 | suffix [-1,0,1,2]
           -1 + 2 -> total 0
            0 + 1 -> total 0

Python implementation

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

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 three_sum: values = sorted(nums)
nums=[-1, 0, 1, 2, -1, -4]; values=[-4, -1, -1, 0, 1, 2]

L3 three_sum: output = []
nums=[-1, 0, 1, 2, -1, -4]; values=[-4, -1, -1, 0, 1, 2]; output=[]

L4 three_sum: for i in range(len(values) - 2):
nums=[-1, 0, 1, 2, -1, -4]; values=[-4, -1, -1, 0, 1, 2]; output=[]; i=0

L7 three_sum: left, right = i + 1, len(values) - 1
nums=[-1, 0, 1, 2, -1, -4]; values=[-4, -1, -1, 0, 1, 2]; output=[]; i=0; left=1; right=5

L9 three_sum: total = values[i] + values[left] + values[right]
nums=[-1, 0, 1, 2, -1, -4]; values=[-4, -1, -1, 0, 1, 2]; output=[]; i=0; left=1; right=5; total=-3

L19 three_sum: left += 1
nums=[-1, 0, 1, 2, -1, -4]; values=[-4, -1, -1, 0, 1, 2]; output=[]; i=0; left=2; right=5; total=-3

L19 three_sum: left += 1
nums=[-1, 0, 1, 2, -1, -4]; values=[-4, -1, -1, 0, 1, 2]; output=[]; i=0; left=3; right=5; total=-3

L9 three_sum: total = values[i] + values[left] + values[right]
nums=[-1, 0, 1, 2, -1, -4]; values=[-4, -1, -1, 0, 1, 2]; output=[]; i=0; left=3; right=5; total=-2

... 13 intermediate state changes omitted ...

L4 three_sum: for i in range(len(values) - 2):
nums=[-1, 0, 1, 2, -1, -4]; values=[-4, -1, -1, 0, 1, 2]; output=[[-1, -1, 2], [-1, 0, 1]]; i=3; left=4; right=3; total=0

L7 three_sum: left, right = i + 1, len(values) - 1
nums=[-1, 0, 1, 2, -1, -4]; values=[-4, -1, -1, 0, 1, 2]; output=[[-1, -1, 2], [-1, 0, 1]]; i=3; left=4; right=5; total=0

L9 three_sum: total = values[i] + values[left] + values[right]
nums=[-1, 0, 1, 2, -1, -4]; values=[-4, -1, -1, 0, 1, 2]; output=[[-1, -1, 2], [-1, 0, 1]]; i=3; left=4; right=5; total=3

L21 three_sum: right -= 1
nums=[-1, 0, 1, 2, -1, -4]; values=[-4, -1, -1, 0, 1, 2]; output=[[-1, -1, 2], [-1, 0, 1]]; i=3; left=4; right=4; total=3

L2 three_sum: values = sorted(nums)
nums=[0, 0, 0, 0]; values=[0, 0, 0, 0]

L3 three_sum: output = []
nums=[0, 0, 0, 0]; values=[0, 0, 0, 0]; output=[]

L4 three_sum: for i in range(len(values) - 2):
nums=[0, 0, 0, 0]; values=[0, 0, 0, 0]; output=[]; i=0

L7 three_sum: left, right = i + 1, len(values) - 1
nums=[0, 0, 0, 0]; values=[0, 0, 0, 0]; output=[]; i=0; left=1; right=3

L9 three_sum: total = values[i] + values[left] + values[right]
nums=[0, 0, 0, 0]; values=[0, 0, 0, 0]; output=[]; i=0; left=1; right=3; total=0

L11 three_sum: output.append([values[i], values[left], values[right]])
nums=[0, 0, 0, 0]; values=[0, 0, 0, 0]; output=[[0, 0, 0]]; i=0; left=1; right=3; total=0

L12 three_sum: left += 1
nums=[0, 0, 0, 0]; values=[0, 0, 0, 0]; output=[[0, 0, 0]]; i=0; left=2; right=3; total=0

L13 three_sum: right -= 1
nums=[0, 0, 0, 0]; values=[0, 0, 0, 0]; output=[[0, 0, 0]]; i=0; left=2; right=2; total=0

L4 three_sum: for i in range(len(values) - 2):
nums=[0, 0, 0, 0]; values=[0, 0, 0, 0]; output=[[0, 0, 0]]; i=1; left=2; right=2; total=0

Why the solution is correct

Every triple has a smallest sorted position that can serve as i, and the two-pointer exclusion proof finds its required suffix pair. Duplicate skipping removes repeated value combinations without eliminating a distinct triple, because equal values have identical sum effects.

Time and space

O(n^2) time; O(n) sorting storage plus the returned triples, which can require O(n^2) space.

Common mistakes

Skipping duplicates before a match without a clear rule can miss valid multiplicities such as [0,0,0]. Indices must remain distinct.

Reasoning card

Transfer exercise

Extend the sorted fixed-prefix strategy to four-sum and account for the extra search dimension.