How Do You Solve 3Sum?

Sort the array, then fix one element at a time and use two pointers to find a pair that completes the triple to zero. The sort is what makes the two pointers possible: once the values are ordered, a comparison between the two pointer values tells you which one to move, and you can rule out entire ranges.

def three_sum(nums):
    values = sorted(nums)
    triples = []
    for i in range(len(values) - 2):
        if i > 0 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:
                triples.append((values[i], values[left], values[right]))
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return triples

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

The output is the two triples of minus one, minus one, two and minus one, zero, one. The sort put the array into the order minus four, minus one, minus one, zero, one, two, and the outer loop skipped the second minus one because the first one already produced every triple containing that value.

The two pointer logic is the standard argument. If the running total is negative, the left value is too small, so you need a larger one and the left pointer moves right. If the total is positive, the right value is too large, so the right pointer moves left. Because the array is sorted, neither move can skip a valid triple.

The trade-off to name is that the sort costs O of n log n time and a copy of the array, and the outer loop then makes the inner scan linear, so the overall bound is O of n squared time with O of n space for the output. That quadratic cost is unavoidable when all triples must be reported, because there can be quadratically many of them. Sorting is worth it here precisely because it turns an unsolvable quadratic search into a quadratic search that never explores the same pair twice.

The two pointer step works because of the same monotonicity that makes it work for two sum. For a fixed first element, the remaining two values live in a sorted suffix. If the running total is negative, then pairing the current left value with any smaller right value would only make it more negative, so the left value cannot be part of a valid pair and you advance it. The mirror argument moves the right pointer inwards when the total is positive. Each pointer move discards a value that provably cannot appear in any remaining solution, so no solution is skipped.

Duplicate handling has two separate sources. The first is duplicate first elements: once you have processed the value at position i, any later position holding the same value would produce exactly the same set of triples, so the code skips it. The second is duplicate pairs within a fixed first element. After finding a match, both pointers move inwards, but that can land on another copy of the same value, which would generate the same triple again. The robust fix is to keep moving past equal values after recording a triple.

The trade-off to name is the output size itself. Three Sum is quadratic in the worst case because there can be quadratically many distinct triples, for example when the array is all zeros, so any correct algorithm must produce that much output. The sort that makes the search efficient costs an extra copy of the array, but the alternative hash-based formulation needs even more memory and gives the same asymptotic time, so the sorted approach is the better trade in practice.