List Every Unique Triplet That Sums to Zero

Medium20–25 min

Topics

ArrayTwo PointerSorting

Companies

AmazonMicrosoftAdobeMeta

Given an integer array nums, find every combination of three different elements whose values add up to zero, and report them with no duplicate triplet appearing twice — a triplet is a duplicate of another if it has the same three values, regardless of which indices produced them. Since the answer is checked as a single flat list of numbers rather than a grouped structure, package your result this way: sort the three values inside each triplet from smallest to largest, then arrange the triplets themselves from smallest to largest (comparing their first value, then second, then third), and concatenate everything into one array. For example, triplets (2, -1, -1) and (0, -1, 1) would be reported together as [-1, -1, 2, -1, 0, 1].

Test Case 1:

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

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

Explanation:Two triplets sum to zero: (-1, -1, 2) and (-1, 0, 1). Each is sorted internally, the two groups are ordered by their first value, then concatenated.

Test Case 2:

Input:nums = [0, 0, 0]

Output:[0, 0, 0]

Explanation:Only one unique triplet exists — the three zeros themselves.

Test Case 3:

Input:nums = [1, 2, -2, -1]

Output:[]

Explanation:No three values here add up to zero, so the result is empty.

Constraints

◆3 ≤ nums.length ≤ 3000
◆-10⁵ ≤ nums[i] ≤ 10⁵

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (integers) — 3-12 integers, separated by commas or spaces.

1	class Solution {
2	public int[] zeroSumTriplets(int[] nums) {
3	Arrays.sort(nums);
4	List<Integer> result = new ArrayList<>();
5	int n = nums.length;
6	for (int i = 0; i < n - 2; i++) {
7	if (i > 0 && nums[i] == nums[i - 1]) continue;
8	int left = i + 1, right = n - 1;
9	while (left < right) {
10	int sum = nums[i] + nums[left] + nums[right];
11	if (sum == 0) {
12	result.add(nums[i]);
13	result.add(nums[left]);
14	result.add(nums[right]);
15	left++;
16	right--;
17	while (left < right && nums[left] == nums[left - 1]) left++;
18	while (left < right && nums[right] == nums[right + 1]) right--;
19	} else if (sum < 0) {
20	left++;
21	} else {
22	right--;
23	}
24	}
25	}
26	int[] flat = new int[result.size()];
27	for (int k = 0; k < flat.length; k++) flat[k] = result.get(k);
28	return flat;
29	}
30	}
31

-4

-1

INITIALIZE

Sort nums first. Original [-1, 0, 1, 2, -1, -4] becomes [-4, -1, -1, 0, 1, 2] — now equal values sit next to each other, which is what makes duplicate-skipping and the two-pointer sweep possible.

Step 1 / 21

Approach & Solutions

Brute Force — Three Nested Loops

Brute

Check every combination of three distinct indices with three nested loops. Whenever a combination sums to zero, sort those three values and use a string key to make sure the same triplet (by value, not index) isn't recorded twice. At the end, sort the collected triplets into the required order and flatten them into one array.

TimeO(n³)

SpaceO(n) for the dedupe set

Java

Try it out

class Solution {
    public int[] zeroSumTriplets(int[] nums) {
        int n = nums.length;
        Set<String> seen = new HashSet<>();
        List<int[]> triplets = new ArrayList<>();
        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) {
                        int[] t = {nums[i], nums[j], nums[k]};
                        Arrays.sort(t);
                        String key = t[0] + "," + t[1] + "," + t[2];
                        if (seen.add(key)) triplets.add(t);
                    }
                }
            }
        }
        triplets.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : (a[1] != b[1] ? a[1] - b[1] : a[2] - b[2]));
        int[] flat = new int[triplets.size() * 3];
        int idx = 0;
        for (int[] t : triplets) {
            flat[idx++] = t[0];
            flat[idx++] = t[1];
            flat[idx++] = t[2];
        }
        return flat;
    }
}

Optimal — Sort + Two Pointer

Optimal

Sort the array first. Walk a single pointer i across it to fix the first number of each triplet (skipping over repeats of the previous i so the same first value isn't tried twice). For the remaining slice, use two pointers — left just after i, right at the end — and slide them toward each other: if the three values sum to zero, record the triplet and step both pointers inward past any duplicate values; if the sum is too small, move left up; if it's too large, move right down. Sorting turns the search for the other two numbers into a single O(n) sweep instead of a nested loop.

TimeO(n²)

SpaceO(1) extra (excluding the sort and output)