A reconciliation job is given signed line items and must find every trio that nets to zero so those three rows can be closed as a matching set. Last quarter the same team needed two invoices that summed to a credit memo — that is Two Sum, and a HashMap of indices was the right bill. This quarter accounting wants unique values, not row numbers. The intern nested three loops and stuffed sorted triples into a Set. A few hundred rows were fine. A few tens of thousands were not.

3Sum wants unique value triplets that add to zero. An array of signed ints is the input. Sorting is legal here because the answer is values, not indexes.

This is an interview writeup, not a two-pointers lecture. The two pointers post owns the left/right walk. Here we only care about fixing i and skipping duplicate values so the tail does not emit the same triple twice. Two Sum kept the array unordered so a map could return indices; a nested HashMap is the wrong default here.

The problem

Given an int[] nums, return every triplet of values at distinct indexes i < j < k such that nums[i] + nums[j] + nums[k] == 0. The same three numbers appear at most once in the result, even if several index triples produce them.

nums = [-1, 0, 1, 2, -1, -4]  →  [-1, -1, 2], [-1, 0, 1]
nums = [0, 1, 1]              →  (empty)
nums = [0, 0, 0]              →  [0, 0, 0]

Note: Two Sum needed indices on an unordered array, so sorting would have fought the return type. Here sorting is the feature: it makes duplicate values adjacent and makes the two-pointer tail legal.

Triple loops plus a set of sorted triples

Every unordered triple of indexes is a candidate. Canonicalize (a, b, c) with a ≤ b ≤ c and drop duplicates through a Set. Correct and cubic.

List<List<Integer>> threeSumNested(int[] nums) {
    Set<List<Integer>> unique = new HashSet<>();
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    List<Integer> t = Arrays.asList(nums[i], nums[j], nums[k]);
                    Collections.sort(t);
                    unique.add(t);
                }
            }
        }
    }
    return new ArrayList<>(unique);
}

At n = 20 this is a rounding error. At production size you paid O(n³) for a question a sort plus a two-pointer tail answers in O(n²): fix i, then two-sum the rest to -nums[i].

Sort, fix i, walk lo and hi

Sort first. For each index i, run opposite-end pointers on i+1 .. n-1:

  • sum < 0 → lo++ (need a larger middle)
  • sum > 0 → hi-- (need a smaller right)
  • sum == 0 → record (nums[i], nums[lo], nums[hi]), then step both and skip duplicate values

Skip i when nums[i] equals nums[i-1]. After a hit, skip lo/hi duplicates the same way. Without those skips, [-1, -1, 0, 1] emits [-1, 0, 1] twice.

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

i=0  val=-4  lo=1  hi=5   -4+-1+2=-3  lo++ until lo==hi, no hit
i=1  val=-1  lo=2  hi=5   -1+-1+2=0   record [-1,-1,2]
             lo=3  hi=4   -1+0+1=0    record [-1,0,1]
i=2  val=-1  skip (duplicate of i=1)
i=3  val=0   lo=4  hi=5   0+1+2=3     no hit

The Java is that walk:

List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> out = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        int lo = i + 1;
        int hi = nums.length - 1;
        while (lo < hi) {
            int sum = nums[i] + nums[lo] + nums[hi];
            if (sum == 0) {
                out.add(List.of(nums[i], nums[lo], nums[hi]));
                lo++;
                hi--;
                while (lo < hi && nums[lo] == nums[lo - 1]) {
                    lo++;
                }
                while (lo < hi && nums[hi] == nums[hi + 1]) {
                    hi--;
                }
            } else if (sum < 0) {
                lo++;
            } else {
                hi--;
            }
        }
    }
    return out;
}

Time is O(n²) after an O(n log n) sort that the nested walk dominates. Space is O(1) extra besides the output list (the sort may use a little scratch). A nested HashMap of complements would hunt indices and still leave you to unique the value triples; it is the Two Sum tool on the wrong prompt.

Note: Skip duplicates at i, then again at lo / hi after a hit. Skipping only i still repeats a triple when the tail has repeated values.

What interviewers usually poke next

  • Target is not zero. Same walk; compare sum to target instead of 0.
  • 3Sum closest. Same i + lo/hi. Track the sum whose absolute distance to the target is smallest; do not collect every hit.
  • 4Sum / k-sum. Fix the first k-2 indexes, two-pointer the tail. Recurse or nest. Same duplicate skip at every fixed index.
  • Duplicates in the input. [0, 0, 0, 0] must return [[0, 0, 0]] once. The skips are the whole follow-up.
  • Overflow. nums[i] + nums[lo] + nums[hi] can wrap int. If they widen the type, name a long sum.

You are done with this problem when you can say, out loud, why Two Sum kept a map and this prompt sorts, why nested loops plus a set are correct, and where the three duplicate skips live.