3Sum - fix one index, then run Two Sum II on the rest

Find every unique triplet that sums to zero. The pattern is not a new pointer trick — it is orchestration: sort once, fix i, squeeze the suffix for -nums[i], and skip duplicates so you never emit the same triplet twice.

LeetCode #15: given an integer array, return all unique triplets [nums[i], nums[j], nums[k]] such that i ≠ j ≠ k and the three values sum to 0. Order inside a triplet does not matter; the result set must not contain duplicates.

The problem

threeSum([-1, 0, 1, 2, -1, -4]) → [[-1,-1,2], [-1,0,1]]
threeSum([0, 1, 1])             → []
threeSum([0, 0, 0])             → [[0,0,0]]

Brute force tries every triple — O(n³). At n=300 that is already tens of millions of additions. The win is reducing each fixed index to a linear two-pointer scan (Day 40), for total O(n²).

Approach 1: Brute force + Set dedupe

function threeSumBrute(nums) {
  const n = nums.length;
  const seen = new Set();
  const out = [];
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      for (let k = j + 1; k < n; k++) {
        if (nums[i] + nums[j] + nums[k] === 0) {
          const t = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);
          const key = t.join(',');
          if (!seen.has(key)) { seen.add(key); out.push(t); }
        }
      }
    }
  }
  return out;
}

Correct. Dedup happens after you find a triple — expensive, and still O(n³) work. Lab n=300: 28,881 μs median.

Approach 2: Sort + fix i + two-pointer squeeze

function threeSum(nums) {
  const a = [...nums].sort((x, y) => x - y);
  const n = a.length;
  const out = [];
  for (let i = 0; i < n - 2; i++) {
    if (i > 0 && a[i] === a[i - 1]) continue; // same fixed value → skip
    if (a[i] > 0) break;                      // rest are ≥ a[i] > 0 → no zero sum
    let l = i + 1, r = n - 1;
    while (l < r) {
      const sum = a[i] + a[l] + a[r];
      if (sum === 0) {
        out.push([a[i], a[l], a[r]]);
        l++; r--;
        while (l < r && a[l] === a[l - 1]) l++; // skip dup L
        while (l < r && a[r] === a[r + 1]) r--; // skip dup R
      } else if (sum < 0) {
        l++; // need bigger pair sum
      } else {
        r--; // need smaller pair sum
      }
    }
  }
  return out;
}

The three moves that make it unique

1. Sort first. Turns the suffix into Two Sum II input. Enables the discard proof from Day 40.
2. Skip equal i. If a[i] === a[i-1], every triple starting with that value was already found.
3. Skip equal L/R after a hit. Without this, [-2,0,0,2,2] would emit [-2,0,2] twice.

Dedup while scanning is the interview skill. A Set of string keys works but hides the pattern and costs memory.

Day 40 inside Day 46

Layer	What it does	From
Outer loop	Fix i, target = -a[i]	Today
Inner squeeze	L/R until sum hits target	Day 40
Skip policy	Equal i / L / R → no duplicate triplets	Today (new)
Unsorted pair only	Hash complement	Day 11 (not needed after sort)

Complexity honesty

Sort is O(n log n). The nested two-pointer work is O(n²) and dominates. Output can itself be O(n²) triplets in the worst case — so “O(n²) time” already includes writing the answer. Extra space beyond the output is O(1) if you sort in place (or O(n) if you copy first, as in the listing above).

Interview soundbite: “I reduce 3Sum to n runs of Two Sum on a sorted suffix, and I skip equal values so uniqueness is free.”

Worked walk

input  [-1, 0, 1, 2, -1, -4]
sorted [-4, -1, -1, 0, 1, 2]

i=-4 → need +4 · L/R never hit · done for this i
i=-1 (first) → need +1
  L=-1, R=2 → -1-1+2=0 → emit [-1,-1,2]
  L=0,  R=1 → -1+0+1=0 → emit [-1,0,1]
i=-1 (second) → SKIP (same as previous i)
i=0 → need 0 · L=1,R=2 → 1+2=3 > 0 → no more
i>0 → break

result: [[-1,-1,2], [-1,0,1]]

When not to use this shape

If the problem needs indices of the three numbers, sorting destroys original positions unless you store (value, index) pairs. If the array is already sorted and you only need one triple (not all unique triples), you can stop at the first hit — but LeetCode #15 wants the full set.

Benchmark — Node, 30-run median

Reproducible pseudo-random arrays in ≈ [-n/4, n/4]. The benchmark script and standalone write-up are not included in this repository.

Approach	n=100 (μs)	n=300 (μs)	n=1K (μs)
Brute + Set	1,525.7	28,881.0	skip
Sort + two-ptr	33.6	121.9	1,607.2

Headline (n=300): two-ptr is 236.9× faster than brute (28,881 → 121.9 μs). At n=1K brute is skipped (≈1e9 ops); two-ptr stays ~1.6 ms.

What breaks? — Anti-patterns

1. Forgetting to skip equal i. Duplicate fixed values re-emit the same triplets. Fix: if (i > 0 && a[i] === a[i-1]) continue.

2. Skipping L/R only before a hit, not after. After a successful triple, the next equal L or R recreates the same pair. Fix: after push, advance then while-skip equals.

3. Hash-set of triplets as the only dedup strategy. Works, but interviewers want the O(1) scan-time skip story. Fix: sort + while-skip; Set is a safety net, not the pattern.

4. Not sorting first, then two-pointer on values. Discard proof requires order (Day 40). Fix: sort (or use O(n²) hash pairs — different pattern).

How it connects

• Day 40 (Two Sum II): the entire inner loop is “find pair summing to target on a sorted array.”
• Day 39 (Valid Palindrome): same converging geometry; here the comparison is sum vs target, not equality of chars.
• Day 11 (Two Sum): unsorted pair → hash. After we sort for 3Sum, hash is optional; two-ptr is the clean fit.

Transfer questions

1. How would you adapt this for 4Sum? What is the new Big-O?
2. Why can we break when a[i] > 0 after sorting?
3. If the problem asked for indices of the three numbers (not values), what breaks in this approach?

Quiz

Your teach step

Close this lesson. Write the “Explain like I’m 10” and the “60-second LinkedIn version” from memory. Focus on: sort → fix i → Day 40 squeeze for -a[i] → skip dups; the 236.9× bench at n=300. Post it, and paste the link.

Questions? Ask the agent — 4Sum sketch, Container With Most Water, or weekly spaced re-test prompts.