3Sum

1. Problem & Core Objective

The problem

Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0.

The solution set must not contain duplicate triplets.

Input:  nums = [-1,0,1,2,-1,-4]     Output: [[-1,-1,2], [-1,0,1]]
Input:  nums = [0,1,1]              Output: []
Input:  nums = [0,0,0]              Output: [[0,0,0]]

Constraints:

• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

What the interviewer is actually testing

The algorithm — sort, fix one element, two-pointer the rest — is straightforward. The entire difficulty is deduplication, and that's what's being marked.

1. Can you extend Two Sum II to three elements? Fix one, two-point the rest.
2. Do you handle duplicate triplets correctly? There are three separate places duplicates can creep in, and missing any one produces wrong output.
3. Do you get i > 0 right in the dedup guard? Writing i >= 0 reads index -1; omitting the guard emits duplicates. This exact pattern reappears in Backtracking.
4. Do you realize sorting is free here? O(n log n) sort inside an O(n²) algorithm costs nothing — and candidates often apologize for it unnecessarily.

Everyone gets a nearly-correct solution. The dedup details separate the passes from the failures.

2. First-Principles Thought Process

Step 1 — Constraints

n up to 3000.

• O(n³) → 2.7 × 10^10. Far too slow.
• O(n²) → 9 × 10^6. Comfortable.
• O(n log n) → trivial.

So O(n²) is the target. That's a strong hint: one loop plus a linear inner scan, not three nested loops.

Step 2 — Reduce to a known problem

Three numbers summing to zero. Rearrange:

a + b + c = 0      ⟺      b + c = -a

So: fix a, then find two numbers summing to -a. That's Two Sum.

Which Two Sum? If the array is sorted, it's Two Sum II — O(n) with two pointers and no extra memory. So:

• Outer loop over a: O(n).
• Inner two-pointer scan: O(n).
• Total: O(n²). Exactly the target.

Step 3 — Should you sort?

Sorting costs O(n log n), but the algorithm is already O(n²), and n log n is dominated by n². The sort is asymptotically free.

And it buys two things:

1. Two pointers become usable (they need order).
2. Equal values become adjacent, which is what makes deduplication cheap.

That second benefit is the one candidates underrate.

Step 4 — Now the real problem: duplicates

nums = [-1, 0, 1, 2, -1, -4] sorts to [-4, -1, -1, 0, 1, 2]. Note there are two -1s.

Without care, the triplet [-1, 0, 1] gets found twice — once anchored at the first -1, once at the second. The output would contain duplicates.

There are three distinct places a duplicate can arise:

(a) The anchor i repeats. If nums[i] == nums[i-1], this anchor produces exactly the same triplets as the previous one did. Skip it.

if (i > 0 && nums[i] == nums[i - 1]) continue;

(b) The left pointer repeats after a hit. Having recorded a triplet, if nums[l] equals the value just used, the same triplet would be found again. Skip forward past the duplicates.

while (l < r && nums[l] == nums[l - 1]) l++;

(c) The right pointer repeats. Symmetric to (b). In practice, fixing (a) and (b) is sufficient — once a and b are pinned down, c is determined, so a duplicate c can't produce a new triplet independently. Skipping on the right as well is harmless and some prefer it for symmetry.

Step 5 — Why i > 0 and not i >= 0

if (i > 0 && nums[i] == nums[i - 1]) continue;

At i == 0 there is no nums[-1]. The i > 0 guard short-circuits before the array access.

Also: skip only when the anchor is a repeat, never the first occurrence. With [-1, -1, 2], the anchor at i=1 (the first -1) must be used — it produces [-1, -1, 2] using the second -1 as b. Only the anchor at i=2 should be skipped.

Step 6 — The early exit

Once sorted, if nums[i] > 0, then nums[l] and nums[r] are both ≥ nums[i] > 0, so the sum is strictly positive and can never be zero. Every remaining anchor is also positive, so you can break out entirely, not just continue.

3. Solution Paths

Approach 1 — Brute force

public List<List<Integer>> threeSum(int[] nums) {
    Set<List<Integer>> res = new HashSet<>();
    Arrays.sort(nums);                                  // to canonicalize triplets

    for (int i = 0; i < nums.length - 2; i++)
        for (int j = i + 1; j < nums.length - 1; j++)
            for (int k = j + 1; k < nums.length; k++)
                if (nums[i] + nums[j] + nums[k] == 0)
                    res.add(Arrays.asList(nums[i], nums[j], nums[k]));

    return new ArrayList<>(res);
}

Deduplication by Set. Sorting first means each triplet is generated in ascending order, so identical triplets produce identical lists — and List compares by content, so the Set deduplicates correctly. (This is exactly why List<Integer> works as a set element while int[] would not — see 05.)

• Time: O(n³).
• Space: O(n) for the result set.

Too slow at n = 3000. Name it, state why, move on.

Counter-questions on this approach

⭐ "Quantify O(n³) at n = 3000 for me."

Roughly 2.7 × 10^10 triples — completely out of reach. The constraint of 3000 is specifically chosen to permit O(n²) and forbid O(n³), which tells me the intended answer is one loop plus a linear inner scan.

"You deduplicate with a Set of triplets. Why does that actually work?"

Because I sort first, so every triplet is generated in ascending order and identical triplets produce equal List objects. List compares by content, so the set deduplicates correctly. It's worth noting this would not work with int[] triplets, which compare by identity.

Approach 2 — Hash set for the third element

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    Set<List<Integer>> res = new LinkedHashSet<>();

    for (int i = 0; i < nums.length - 2; i++) {
        Set<Integer> seen = new HashSet<>();
        for (int j = i + 1; j < nums.length; j++) {
            int need = -nums[i] - nums[j];
            if (seen.contains(need)) {
                res.add(Arrays.asList(nums[i], need, nums[j]));   // sorted order
            }
            seen.add(nums[j]);
        }
    }
    return new ArrayList<>(res);
}

How it works. Fix a, then run the unsorted Two Sum (hash-based) on the remainder.

• Time: O(n²).
• Space: O(n) for the inner set, plus the result.

Correct and optimal in time, but it needs a Set for deduplication and O(n) extra space. The two-pointer version dedups by skipping and uses O(1) extra space. Worth mentioning as a valid alternative — especially if you can't recall the skip logic under pressure.

Counter-questions on this approach

⭐ "This is already O(n²) — the same as your optimal. Why go further?"

Space. It needs an inner Set per anchor and a Set of result triplets to deduplicate — O(n) extra either way. The sort-plus-two-pointers version deduplicates by index skipping, which is O(1). Same time, strictly less memory.

"Why does this version still need a Set for the results?"

Because without sorted adjacency there's no cheap local test for "have I already emitted this triplet". Sorting is what makes duplicates neighbours, and therefore checkable with a single comparison.

Approach 3 — Sort + two pointers (optimal)

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();

    for (int i = 0; i < nums.length - 2; i++) {
        if (nums[i] > 0) break;                              // (1) early exit
        if (i > 0 && nums[i] == nums[i - 1]) continue;       // (2) skip duplicate anchors

        int l = i + 1, r = nums.length - 1;
        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];

            if (sum < 0) {
                l++;
            } else if (sum > 0) {
                r--;
            } else {
                res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                l++;
                r--;
                while (l < r && nums[l] == nums[l - 1]) l++;  // (3) skip duplicate seconds
            }
        }
    }
    return res;
}

Full trace on nums = [-1, 0, 1, 2, -1, -4]. Sorted: [-4, -1, -1, 0, 1, 2]

Result: [[-1,-1,2], [-1,0,1]] ✓

Notice i = 2. Without the dedup guard, that anchor would produce [-1, 0, 1] a second time. This is the trace to walk through in an interview.

• Time: O(n²) — the O(n log n) sort is dominated by the O(n) outer loop × O(n) inner scan.
• Space: O(1) extra (excluding the output), plus O(log n) for the sort's stack.

Counter-questions on this approach

⭐ "Why i > 0 and not i >= 0 in the dedup guard?"

At i == 0 there is no nums[-1]. Java's && short-circuits, so i > 0 && means the array access never happens at index 0. Writing i >= 0 would evaluate nums[-1] and throw on the very first iteration.

⭐ "Walk me through why [0,0,0,0] produces one triplet and not several."

Sorted it's [0,0,0,0]. The anchor at i = 0 runs the scan and records [0,0,0]. At i = 1 the guard sees nums[1] == nums[0] and skips, because that anchor would regenerate exactly the same triplet; same at i = 2. One triplet is emitted. Verified: removing the anchor guard produces two.

"Isn't sorting expensive? You've added O(n log n) to the problem."

It's asymptotically free — the scan is O(n²), which dominates entirely. And it buys two things: the two-pointer scan becomes possible at all, and equal values become adjacent, which turns deduplication into an O(1) neighbour comparison instead of a set of canonical triplets.

"Why do you move both pointers after recording a triplet?"

The sum was exactly zero. Moving only l makes it strictly positive; moving only r makes it strictly negative. Neither can produce another zero with the other pointer fixed, so moving one alone just wastes an iteration.

"Why skip duplicates after recording rather than before?"

Because I must record the triplet first, then advance past repeats of the element I just consumed. Skipping before recording would discard valid triplets that use that value legitimately — as in [-2,0,1,1,2], where both 1s belong to the same answer.

The three dedup details, isolated

(1) Anchor dedup — i > 0 && nums[i] == nums[i-1]

The i > 0 prevents reading index -1. Skipping only repeats means the first occurrence of each value is always used.

(2) Second-element dedup — after recording, not before

res.add(...);
l++; r--;
while (l < r && nums[l] == nums[l - 1]) l++;   // NOW skip past repeats

Order matters: you must record the triplet first, then advance past duplicates of the element you just consumed. Skipping before recording would lose valid triplets.

(3) Moving both pointers on a hit

l++; r--;

Advancing only one would keep the other fixed, and since the sum was exactly zero, moving just l makes the sum positive and just r makes it negative — you'd never find another triplet with this anchor from that position. Moving both keeps the scan correct and is required for progress.

Comparison

4. Why the Optimal Wins

Against brute force. Three nested loops try every triple. Sorting plus two pointers replaces the innermost two loops with a single linear scan, because the ordering lets one comparison eliminate a whole range of candidates — the elimination argument from Two Sum II. O(n³) → O(n²).

Against the hash-set version. Both are O(n²) time, so the difference is space and mechanism:

• The hash version needs an O(n) inner set and a Set of result triplets to deduplicate. The two-pointer version needs neither — sortedness makes duplicates adjacent, so skipping them is an O(1) index comparison.
• Sorting therefore does double duty: it enables the two pointers and it makes deduplication nearly free.

The point worth stating about the sort:

"Sorting is O(n log n), but the scan is O(n²), which dominates. So the sort is asymptotically free — and it buys me both the two-pointer scan and cheap deduplication. That's two benefits for no asymptotic cost."

Candidates often apologize for sorting. Don't — here it's the enabling step.

Why O(n²) is the floor for this approach. There can be O(n²) triplets in the output (consider many zeros), so you cannot beat O(n²) in the worst case simply because of the output size. Better algorithms exist only in restricted settings.

5. Java Prerequisites

Sorting primitives

Arrays.sort(nums);        // ascending, dual-pivot quicksort, O(n log n)

No comparator overload exists for int[] — see 04 §5.1. Ascending is what you want anyway.

This mutates the caller's array. Ask whether that's acceptable; if not, sort a clone.

Building the triplet

res.add(Arrays.asList(nums[i], nums[l], nums[r]));
res.add(List.of(nums[i], nums[l], nums[r]));            // Java 9+, immutable

Arrays.asList boxes the ints into Integers automatically. Both work; List.of rejects nulls (irrelevant here) and is immutable.

Loop bound nums.length - 2

for (int i = 0; i < nums.length - 2; i++)

You need at least two elements after i to form a triplet. Using nums.length instead would leave l >= r on the last iterations — harmless (the while wouldn't run) but it signals imprecision.

Since n >= 3 is guaranteed, nums.length - 2 is always at least 1, so there's no underflow risk.

Guarding array access with &&

if (i > 0 && nums[i] == nums[i - 1]) continue;

Java's && short-circuits: if i > 0 is false, nums[i-1] is never evaluated. Reversing the operands would throw ArrayIndexOutOfBoundsException at i = 0.

break vs continue

if (nums[i] > 0) break;        // stop entirely — all later anchors are also positive
if (duplicate) continue;        // skip this one, keep going

On sorted input, break is correct for the positivity check because every subsequent anchor is ≥ this one. Using continue there would still be correct, just slower.

Overflow

int sum = nums[i] + nums[l] + nums[r];

Values are bounded by ±10^5, so the sum is at most 3 × 10^5 — comfortably within int. Say that you checked; with larger bounds you'd need long.

6. Interview Communication Guide

Clarifying questions

1. "Should the output contain unique triplets by value, or unique index combinations?" — by value. This is the crux; [-1,0,1] found via different indices counts once.
2. "Can I modify the input array by sorting it?"
3. "Does the order of triplets, or of elements within a triplet, matter?" — no, per the problem.
4. "Can the same element be used more than once?" — no; indices must be distinct. But equal values at different indices are fine, which is why [0,0,0] is valid.
5. "Can the array contain fewer than 3 elements?" — constraints say n >= 3.

The pitch

"Three numbers summing to zero. If I fix one — call it a — then I need two numbers summing to -a. That's Two Sum.

If I sort first, I can use the two-pointer version of Two Sum, which is O(n) and needs no extra space. So: sort, loop over each element as the anchor, and two-point the remainder. That's O(n) outer times O(n) inner, so O(n²) — which fits n = 3000.

The sort is O(n log n), dominated by the O(n²) scan, so it's asymptotically free. And it gives me a second benefit: equal values become adjacent, which makes deduplication cheap.

Deduplication is really the hard part. Duplicates can arise in two places. First, if the anchor value repeats, it produces exactly the same triplets as before — so I skip it with i > 0 && nums[i] == nums[i-1]. The i > 0 matters because at i = 0 there's no previous element. Second, after recording a triplet I advance past any repeats of the left value, so the same triplet isn't found again.

I'll also break early once the anchor is positive — with everything sorted, the sum can only be positive from there on."

Edge cases to raise proactively

[0,0,0,0] and [-2,0,1,1,2] are the two to volunteer. The first tests anchor dedup. The second is subtler: the two 1s must both be usable within one triplet, so your dedup must not be so aggressive that it blocks legitimate repeated values. That distinction — skip duplicate anchors, but allow duplicate values inside a triplet — is what the i > start-style logic is really encoding, and it reappears verbatim in Backtracking.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. These are new problems, asked after your solution is accepted — not challenges to it. (Those are the counter-questions attached to each approach in §3.) ⭐ marks the most likely.

⭐ "4Sum?"

Same structure with one more loop: sort, fix i and j with two nested loops, two-point the remainder. O(n³), with the same dedup guard at each level. Generalizes to k-Sum at O(n^(k−1)) — a recursive kSum helper that bottoms out at the two-pointer case.

One caution: with four values the sum can overflow int for large bounds, so widen to long.

"3Sum Closest — find the triplet with sum nearest a target."

Same scan, but instead of testing for equality you track the minimum |sum − target| seen. No deduplication needed, since you return a single number rather than a set of triplets. Slightly easier than this problem.

"3Sum Smaller — count triplets with sum below a target."

When nums[i] + nums[l] + nums[r] < target, then every r between l+1 and the current r also works — so add r - l to the count in one step and advance l. Counting in bulk keeps it O(n²).

"What if you couldn't sort — say the original indices were needed?"

Use the hash-set approach: fix a, then hash-based Two Sum on the remainder. O(n²) time, O(n) space, with a Set for dedup. That's the version to reach for whenever sorting is off the table.

"Can you do better than O(n²)?"

Not in general. The output alone can contain O(n²) triplets, so you can't beat O(n²) just to write the answer. 3SUM is also a classic problem conjectured to have no substantially sub-quadratic solution — the "3SUM-hardness" conjecture, which is used to prove lower bounds for other problems. Mentioning that is a genuine depth signal.