13 · 3Sum

In an Xcode test target:

import Testing

struct ThreeSumTests {

    @Test(arguments: [
        ([-2, 0, 1, 1, 2], [[-2, 0, 2], [-2, 1, 1]]),
        ([0, 0, 0, 0], [[0, 0, 0]]),
        ([1, 2, -4], []),
    ])
    func returnsEveryDistinctTripletThatSumsToZero(numbers: [Int], expected: [[Int]]) {
        #expect(normalised(threeSum(numbers)) == expected)
    }

    // MARK: - Privates
    private func threeSum(_ numbers: [Int]) -> [[Int]] {
        []
    }

    /// Triplet order and the order inside a triplet are free, so compare a sorted copy.
    private func normalised(_ triplets: [[Int]]) -> [[Int]] {
        triplets
            .map { $0.sorted() }
            .sorted { $0.lexicographicallyPrecedes($1) }
    }
}

In a playground:

func threeSum(_ numbers: [Int]) -> [[Int]] {
    [] // your solution
}

/// Triplet order and the order inside a triplet are free, so compare a sorted copy.
func normalised(_ triplets: [[Int]]) -> [[Int]] {
    triplets
        .map { $0.sorted() }
        .sorted { $0.lexicographicallyPrecedes($1) }
}

let cases: [([Int], [[Int]])] = [
    ([-2, 0, 1, 1, 2], [[-2, 0, 2], [-2, 1, 1]]),
    ([0, 0, 0, 0], [[0, 0, 0]]),
    ([1, 2, -4], []),
]
for (numbers, expected) in cases {
    let got = normalised(threeSum(numbers))
    print(got == expected ? "PASS" : "FAIL", numbers, "→", got, "expected", expected)
}

Sort, then two pointers inside a loop. The cue is "groups of three" that "add up to" a target, with "distinct" groups. Fix the first value and what remains is problem 12 exactly: find two entries in a sorted range that sum to minus the first value. Sorting is what makes both halves work — it enables the two-pointer search, and it puts equal values next to each other so repeats can be skipped instead of filtered out afterwards.

Sort the numbers. Take each value in turn as the first member of a group, skipping it if it is the same as the value just before (it would find the same groups again). For each first value, run the two-finger search from problem 12 on everything to its right, looking for a pair that brings the total to zero. When a pair is found, record the group, move both fingers inward, and move the left finger past any copies of the value it just used. Once the first value is above zero you can stop: everything to its right is at least as large, so no group can add up to zero.

Time O(n²): the sort is O(n log n), then n first values each run an O(n) scan. Space O(1) beyond the output, or O(n) if you count the sorted copy — Swift's sorted() returns a new array, and sorting the input in place would change the caller's data.

func threeSum(_ numbers: [Int]) -> [[Int]] {
    let sorted = numbers.sorted()
    var triplets: [[Int]] = []

    for first in sorted.indices {
        if sorted[first] > 0 { break }                                   // nothing to the right can bring it back to 0
        if first > 0 && sorted[first] == sorted[first - 1] { continue }  // same first value, same triplets

        var left = first + 1
        var right = sorted.count - 1
        while left < right {
            let sum = sorted[first] + sorted[left] + sorted[right]
            if sum < 0 {
                left += 1
            } else if sum > 0 {
                right -= 1
            } else {
                triplets.append([sorted[first], sorted[left], sorted[right]])
                left += 1
                right -= 1
                while left < right && sorted[left] == sorted[left - 1] { left += 1 }
            }
        }
    }
    return triplets
}

Skipping repeats of the left value is enough: once left has moved past its copies, the right value that completes the group is fixed, so a duplicate on the right can't produce a new match.

Verified with swift test on Swift 6.4 in Swift 6 mode: the three examples above, six more (empty, one and two entries, a seven-value mix with three answers, fifteen values heavy with repeats, and [-1, -1, -1, 2, 2]), and 2,000 random arrays checked against a brute-force O(n³) search — including a check that no group comes back twice.

[-2, 0, 1, 1, 2] (already sorted)

Two groups.

[0, 0, 0, 0] — first value is the zero at position 0; left at 1, right at 3, sum 0, record [0, 0, 0]; both move to 2 and meet. Positions 1, 2 and 3 as first value are all repeats of 0 and are skipped. One group.

A tuple can't go in a Set. The instinct is to collect every match into a set to remove repeats — Set<(Int, Int, Int)> — and it doesn't compile, because tuples aren't Hashable in Swift. Set<[Int]> does compile, but only if every group is sorted first, and it adds O(k) hashing for k results plus a conversion back to an array at the end. It is a working answer, and an interviewer will accept it with a nudge; skipping repeats in the sorted array is the one they are waiting for, and it removes the need for the set entirely. Say both, write the second.

• "Closest sum to a target instead of exactly zero." → Same loop; track the sum with the smallest distance to the target and move the fingers by comparing with the target. No duplicate-skipping needed.
• "4Sum." → Two nested loops for the first two values, each skipping repeats, then the two-finger scan: O(n³). Generalises to k-sum by recursion down to two.
• "Can you beat O(n²)?" → Not in general — 3Sum is the textbook problem believed to need about n² time. Saying that is a better answer than inventing an optimisation.