3Sum

Return every unique triplet whose values sum to zero without repeating duplicate triplets.

Open concept page Back to problem map

This is the classic upgrade path from pair-sum reasoning to triplet reasoning.

It is also a great exercise in duplicate handling after sorting.

Problem intuition

The brute-force approach checks every triple and deduplicates with a set.

The better route sorts first, fixes one number, and then solves the remaining pair with two pointers while skipping duplicates.

Java solution ladder

The solutions below are ordered from least optimal to most optimal, so you can see the improvement path instead of only the final answer.

Solution 1

Triple nested loops with a set

O(n^3)O(k)

Try every triplet, sort the chosen values locally, and use a set to avoid duplicates. Correct but expensive.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> set = new HashSet<>();

        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        int[] triple = new int[] {nums[i], nums[j], nums[k]};
                        Arrays.sort(triple);
                        set.add(Arrays.asList(triple[0], triple[1], triple[2]));
                    }
                }
            }
        }

        return new ArrayList<>(set);
    }
}

Solution 2

Sort and solve remaining pair with two pointers

O(n^2)O(1) extra excluding output

Sort once, fix one number, then move two pointers for the remaining sum while skipping duplicates.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

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

        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;

                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }

                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return result;
    }
}