3Sum

Start from brute force

The obvious approach tries every triple of positions: three nested loops over i < j < k, and whenever nums[i] + nums[j] + nums[k] == 0, add the sorted triplet to a set so duplicates collapse, then sort the set for the output. It is correct, because every combination is checked, and it needs O(t) space for the t distinct triplets. But it is O(n³) time: at n = 3000, a common limit for this problem, that is about 4.5 billion triples, while the sorted two-pointer version does about 4.5 million pointer steps. The set also hides duplicate work rather than avoiding it: [0, 0, 0, 0] finds the same triplet four times.

The approach

Sorting turns the inner search into a two-pointer squeeze. Fix the smallest element a[i]; you need a pair in the rest that sums to −a[i]. With lo just after i and hi at the end, a sum that is too small can only grow by moving lo right, and one that is too big can only shrink by moving hi left, so each step discards a value that cannot be in any remaining pair. Sorting also makes duplicates adjacent, so skipping a value equal to its neighbor is enough to emit each triplet once, already in order.

The reference sorts into a, then for each i in range(n - 2) skips a[i] == a[i - 1]. Inside, it computes s = a[i] + a[lo] + a[hi]: below 0 it does lo += 1, above 0 hi -= 1, and at 0 it appends [a[i], a[lo], a[hi]], moves both pointers, and steps past repeats of the values just used. Because i and lo only increase, the triplets come out in lexicographic order with no final sort.

Walk through an example

Trace the first example, which sorts to a = [-4, -1, -1, 0, 1, 2].

Complexity

Optimal: O(n²) time, an O(n) two-pointer pass for each of n values of i after an O(n log n) sort; O(n) space for the sorted copy a, plus the output. Brute force (three nested loops and a set): O(n³) time and O(t) space for t distinct triplets.

Edge cases to test

• Fewer than three numbers: [1, -1], [5] and [] all return [], because range(n - 2) is empty.
• All zeros: [0, 0, 0, 0] → [[0, 0, 0]], once rather than four times.
• Heavy duplicates: [-2, -2, 0, 0, 2, 2] → [[-2, 0, 2]]. All three skips matter: at i, at lo and at hi.
• Equal values used together: [-1, -1, 2] → [[-1, -1, 2]]. Duplicate skipping must remove repeated triplets, not stop two equal numbers from appearing in one triplet.
• No negatives: [1, 2, 3] → []. Once a[i] > 0 no triplet can sum to zero, so a break there is a safe shortcut the reference does not take.
• Large magnitudes: Python integers cannot overflow, but in a language with 32-bit integers a[i] + a[lo] + a[hi] can, so use a 64-bit sum.

Common mistakes

• Brute-forcing all triples in O(n³) instead of collapsing the inner search with two pointers.
• Not skipping duplicates, so the result contains repeated triplets.
• Advancing only one pointer on a match, or forgetting to move past duplicate values after recording one.
• Skipping duplicates at i by comparing with a[i + 1] instead of a[i - 1]: that skips the first copy of a value, so the first example loses [-1, -1, 2].

Follow-ups an interviewer asks next

How does this change for 3Sum Closest?

Keep the same sort and two-pointer loop, but instead of looking for an exact zero, track the sum s with the smallest abs(s - target) seen so far, and move lo or hi depending on whether s is below or above the target. Return early if a sum hits the target exactly. Duplicate skipping becomes optional, since only one number is returned. Time stays O(n²).

How do you generalize to 4Sum or k-Sum?

Recursively: fix one element, skip its duplicates, and solve a (k − 1)-sum on the rest with the reduced target, down to the two-pointer base case. That gives O(n^(k−1)) time after one sort. For 4Sum it is O(n³); a hash map of pair sums can decide whether any quadruplet exists in about O(n²) average time, but listing every unique one that way is harder to deduplicate.

Can you solve it with a hash set instead of two pointers?

Yes: for each i, run a Two Sum pass over the rest with a set of seen values, looking for -(a[i] + x). It is also O(n²) but uses O(n) extra space per pass, and deduplication needs a set of sorted tuples. You still have to sort to produce the required output order, so the two-pointer version is usually simpler.

Can 3Sum be solved faster than O(n²)?

Only by small factors. Algorithms exist that shave logarithmic factors off n², but no algorithm running in O(n^(2−ε)) for any constant ε > 0 is known. The 3SUM conjecture says none exists, and many problems in computational geometry are shown hard by reducing 3SUM to them.

Where this shows up

Three-sum is the canonical “sort, then two pointers to collapse a dimension” pattern — trading an O(n³) search for O(n²) by exploiting order. The same reduction recurs across pair-, triple-, and k-sum problems and in any search where sortedness lets you prune half the space each step.

Reference solution

def three_sum(nums):
    a = sorted(nums)
    n = len(a)
    out = []
    for i in range(n - 2):
        if i > 0 and a[i] == a[i - 1]:
            continue
        lo, hi = i + 1, n - 1
        while lo < hi:
            s = a[i] + a[lo] + a[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                out.append([a[i], a[lo], a[hi]])
                lo += 1
                hi -= 1
                while lo < hi and a[lo] == a[lo - 1]:
                    lo += 1
                while lo < hi and a[hi] == a[hi + 1]:
                    hi -= 1
    return out


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

function threeSum(nums: number[]): number[][] {
  const a = [...nums].sort((x, y) => x - y);
  const n = a.length;
  const out: number[][] = [];
  for (let i = 0; i < n - 2; i++) {
    if (i > 0 && a[i] === a[i - 1]) continue;
    let lo = i + 1, hi = n - 1;
    while (lo < hi) {
      const s = a[i] + a[lo] + a[hi];
      if (s < 0) lo++;
      else if (s > 0) hi--;
      else {
        out.push([a[i], a[lo], a[hi]]);
        lo++; hi--;
        while (lo < hi && a[lo] === a[lo - 1]) lo++;
        while (lo < hi && a[hi] === a[hi + 1]) hi--;
      }
    }
  }
  return out;
}

console.log(threeSum([-1, 0, 1, 2, -1, -4]));   // -> [[-1,-1,2],[-1,0,1]]