3Sum

Introduction

3Sum is Two Sum’s older sibling. Once you internalize the move from Two Sum — replace an inner search with a lookup — 3Sum looks like a trivial extension: fix one element $a_i$ and ask “is there a Two Sum for target $-a_i$ in the rest of the array?” That is the algorithmic content of the problem.

It is also not what the problem is actually testing.

The real grading criterion for 3Sum, at every company that asks it, is deduplication. Almost every candidate can see the reduction to Two Sum inside ninety seconds. A smaller fraction can implement it without bugs. A much smaller fraction produces a correct, deduped output on the first run — without either (a) double-counting triplets like $(0, 0, 0)$, or (b) silently dropping one of two legitimately distinct triplets that happen to share an element. That delta is where the signal lives.

3Sum is not really about 3Sum. It is about writing the deduplication argument before you write the loop that needs it.

This chapter takes the Two Sum move as given and spends most of its energy on the part the interview actually scores: sorting so dedup becomes a one-liner, the two-pointer skip step, and the handful of edge cases where a naive implementation quietly produces the wrong set.

What the interviewer is actually testing

Read off the checklist out loud; interviewers track it even when they don’t tell you so:

1. Pattern recognition. Do you see the reduction to Two Sum in under a minute?
2. Clarification discipline. Do you ask about duplicates in the input and duplicates in the output — two different questions — before you write code?
3. Dedup strategy. Do you have a defensible plan for deduplication, or are you hoping a hash set will bail you out at the end?
4. Correct bounds. Do the two inner loops on your sorted array actually stop correctly when the pointers meet, and do you skip duplicates on both sides of an emit?
5. Complexity articulation. Can you argue $O(n^2)$ without hand-waving, and can you argue why $O(n^2)$ is the lower bound for this family?

Problem statement

Clarifying questions — and why each one matters

3Sum arrives under-specified in two very specific ways. If you ask the two questions below in your first minute, you have already passed a signal the interviewer is waiting for.

A mental framework for k-Sum problems

3Sum is the first step on a ladder. The same reduction applies to 4Sum, 5Sum, k-Sum:

1. Sort. This is not optional for the recommended solution. Sorting turns deduplication from a data-structure problem into a one-liner (skip equal neighbours).
2. Fix $k-2$ elements with outer loops. Each outer loop iterates over candidate values, skipping duplicates.
3. Reduce the innermost pair to Two Sum on a sorted array. Two-pointer walk — the O(n) core from the Two Sum chapter’s two-pointer section.
4. At the emit, advance past duplicates on both sides. This is the dedup step that makes the output unique without a separate hash set.
5. Early-exit when the sorted prefix can no longer hit the target. At $A[i] > 0$ the minimum remaining triplet is already positive; stop.

Total complexity: $O(n^{k-1})$ time, $O(1)$ extra space after sorting. For 3Sum, that is $O(n^2)$.

Every $k$-Sum variant you will ever be asked is this skeleton with a different outer loop count. Internalize the skeleton here; you will never re-derive it.

Discussion

#include <algorithm>
#include <vector>

// Enumerate every triple (i < j < k). Cubic time, constant extra space.
// Produces a deduplicated set of triplets by sorting each triplet and then
// the output — simple but slow.
std::vector<std::vector<int>> threeSum(std::vector<int> A) {
    std::vector<std::vector<int>> out;
    const int n = static_cast<int>(A.size());

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            for (int k = j + 1; k < n; ++k) {
                if (A[i] + A[j] + A[k] == 0) {
                    std::vector<int> t = {A[i], A[j], A[k]};
                    std::sort(t.begin(), t.end());
                    out.push_back(std::move(t));
                }
            }
        }
    }

    // Dedup the output; the triplets themselves were already sorted above.
    std::sort(out.begin(), out.end());
    out.erase(std::unique(out.begin(), out.end()), out.end());
    return out;
}

#include <algorithm>
#include <set>
#include <unordered_set>
#include <vector>

// Fix one element A[i] and reduce the remaining problem to Two Sum on
// a target of -A[i]. Expected O(n^2) time, O(n) extra space.
//
// Deduplication is awkward: we have to canonicalize each triplet and
// push it through a set, because the hashing pass does not know which
// value it already emitted at the current pivot.
std::vector<std::vector<int>> threeSum(std::vector<int> A) {
    std::sort(A.begin(), A.end());  // only to canonicalize triplets for dedup
    const int n = static_cast<int>(A.size());

    std::set<std::vector<int>> unique;

    for (int i = 0; i < n - 2; ++i) {
        // Skip duplicates at the pivot, or the inner loop wastes work
        // re-finding the same triplets.
        if (i > 0 && A[i] == A[i - 1]) continue;

        const int target = -A[i];
        std::unordered_set<int> seen;
        for (int j = i + 1; j < n; ++j) {
            const int complement = target - A[j];
            if (seen.count(complement)) {
                // A[i] <= complement <= A[j] because the array is sorted
                // and we scan j left-to-right, so this is already canonical.
                unique.insert({A[i], complement, A[j]});
            }
            seen.insert(A[j]);
        }
    }

    return {unique.begin(), unique.end()};
}

#include <algorithm>
#include <vector>

// Sort once, then fix A[i] and two-pointer the rest. O(n^2) time,
// O(1) extra space (ignoring the output vector and the sort's own
// stack usage). Deduplication falls out naturally from the sort.
std::vector<std::vector<int>> threeSum(std::vector<int> A) {
    std::sort(A.begin(), A.end());
    const int n = static_cast<int>(A.size());

    std::vector<std::vector<int>> out;

    for (int i = 0; i < n - 2; ++i) {
        // Early exit: the smallest possible triplet starting here is
        // already positive, so no later i can hit zero either.
        if (A[i] > 0) break;
        // Skip duplicate pivots so we never emit the same triplet twice.
        if (i > 0 && A[i] == A[i - 1]) continue;

        int lo = i + 1;
        int hi = n - 1;
        while (lo < hi) {
            const int s = A[i] + A[lo] + A[hi];
            if (s == 0) {
                out.push_back({A[i], A[lo], A[hi]});
                // Advance past duplicates on BOTH sides before stepping.
                // This is the dedup trick that makes the sort pay off.
                while (lo < hi && A[lo] == A[lo + 1]) ++lo;
                while (lo < hi && A[hi] == A[hi - 1]) --hi;
                ++lo;
                --hi;
            } else if (s < 0) {
                ++lo;  // Sum too small: the only way to grow it is to raise lo.
            } else {
                --hi;  // Sum too large: the only way to shrink it is to lower hi.
            }
        }
    }

    return out;
}

Approach comparison

Default answer: sort + two pointers. State the reduction to Two Sum, state the sort, state the dedup argument, then write the code.

Follow-ups to anticipate

Pattern recognition — the real lesson

The move you practiced here — fix an outer element, reduce to the $(k-1)$-sum problem on the suffix, let sort carry the dedup — reappears in every $k$-sum variant and in a surprising number of problems that don’t look like $k$-sum at first:

• 4Sum, k-Sum. Direct application.
• 3Sum Closest, 3Sum Smaller. Same walk, different emit condition.
• Triangle count (count triples $a, b, c$ with $a + b > c$). Sort, fix the longest side, two-pointer the rest.
• Subarray Product Less Than K. Not $k$-sum, but the same move both pointers monotonically on a sorted (or windowed) range pattern.
• Minimum Triangle Perimeter. Sort, then consecutive triples — a simpler cousin of this skeleton.

More deeply, this chapter is the second argument in a running theme: whenever an interview problem asks for unordered combinations of array elements satisfying a constraint, sorting is almost always the right first instruction, because it turns enumerate without duplicates from an algorithm design problem into three while guards.

What to say out loud — the delivery script

Rehearse this until it’s automatic:

1. Restate the problem. “I need every unique triplet of elements from $A$ that sums to zero. Duplicates in the input are allowed; duplicates in the output are not.”
2. Ask the two clarifications. Dedup semantics, and whether you can modify the input.
3. Name the reduction. “If I fix one element $A[i]$, this becomes Two Sum on the suffix with target $-A[i]$.”
4. State the plan. “I’ll sort so dedup is a neighbour check, then for each pivot run a two-pointer walk on the rest. $O(n^2)$ time, $O(1)$ extra space.”
5. Write it. The three whiles are the part worth writing slowly.
6. Trace through [-1, 0, 1, 2, -1, -4]. Narrate the pivot skips and the emit-plus-advance on both sides.
7. State the dedup claim out loud. “Outer skip handles duplicate pivots; inner skips handle duplicate emits; together they guarantee each triplet emits exactly once.”
8. Call out the trap cases. [0, 0, 0, 0] and [-2, 0, 1, 1, 2].
9. Summarize. ”$O(n^2)$ is optimal in the general case because the output itself can be quadratic.”

Delivery is scored. The candidate who says “dedup falls out of the sort” is ahead of the candidate who writes the same code silently.

Summary

3Sum is Two Sum with one more pointer — and one much harder editorial problem: how do you not emit the same triplet twice? The answer is almost never “stuff everything in a hash set at the end”; it is “sort first, then skip duplicates on both sides of every emit.” That move generalizes directly to every $k$-Sum variant you will ever be asked.

Internalize the skeleton: sort, fix $k - 2$ elements with outer loops, two-pointer the innermost pair, skip neighbours on both sides after each emit, early-exit when the sorted prefix can no longer hit the target. Every k-sum problem on every problem sheet collapses to that skeleton. The point of 3Sum is to build the reflex.