Triplets With a Sum of 0 (3Sum)

Given an array of integers, find all unique triplets [a, b, c] of elements (at different positions) with a + b + c = 0. Each triplet is in ascending order, and the same triplet must not appear twice.

LeetCode: 15. 3Sum

Example

Text

Input:  [-1, 0, 1, 2, -1, -4]    Output: [[-1, -1, 2], [-1, 0, 1]]
Input:  [1, -2, 1, 0, 5]         Output: [[-2, 1, 1]]

Brute force: three nested loops

Sort the array first, so every triplet comes out in ascending order, and collect the triplets into a TreeSet to drop duplicates. A triplet is a List<Integer>, which has value-based equals, unlike an int[]. The TreeSet takes a comparator that compares the three elements in order, so the result is sorted.

Java

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

public class Main {
    static int compare(List<Integer> x, List<Integer> y) {
        for (int i = 0; i < 3; i++) {
            int c = Integer.compare(x.get(i), y.get(i));
            if (c != 0) return c;
        }
        return 0;
    }

    static List<List<Integer>> threeSum(int[] nums) {
        int[] a = nums.clone();
        Arrays.sort(a);
        int n = a.length;
        Set<List<Integer>> found = new TreeSet<>(Main::compare);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (a[i] + a[j] + a[k] == 0) {
                        found.add(List.of(a[i], a[j], a[k]));
                    }
                }
            }
        }
        return new ArrayList<>(found);
    }

    public static void main(String[] args) {
        System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
        System.out.println(threeSum(new int[]{1, -2, 1, 0, 5}));
    }
}

Output

[[-1, -1, 2], [-1, 0, 1]]
[[-2, 1, 1]]

Time: O(n³). Space: O(t) for t distinct triplets.

Better: look up the third value

Fixing a[i] and a[j] determines the third value: -(a[i] + a[j]). Instead of a third loop, look it up in a HashSet of the values seen between i and j, as in Two Sum.

Java

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

public class Main {
    static int compare(List<Integer> x, List<Integer> y) {
        for (int i = 0; i < 3; i++) {
            int c = Integer.compare(x.get(i), y.get(i));
            if (c != 0) return c;
        }
        return 0;
    }

    static List<List<Integer>> threeSum(int[] nums) {
        int[] a = nums.clone();
        Arrays.sort(a);
        Set<List<Integer>> found = new TreeSet<>(Main::compare);
        for (int i = 0; i < a.length; i++) {
            Set<Integer> seen = new HashSet<>();
            for (int j = i + 1; j < a.length; j++) {
                int third = -(a[i] + a[j]);
                if (seen.contains(third)) {
                    found.add(List.of(a[i], third, a[j])); // a[i] <= third <= a[j]
                }
                seen.add(a[j]);
            }
        }
        return new ArrayList<>(found);
    }

    public static void main(String[] args) {
        System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
        System.out.println(threeSum(new int[]{1, -2, 1, 0, 5}));
    }
}

Output

[[-1, -1, 2], [-1, 0, 1]]
[[-2, 1, 1]]

Time: O(n²) on average. Space: O(n) for the set.

third was seen at a position between i and j of the sorted array, so it lies between a[i] and a[j], and [a[i], third, a[j]] is already in ascending order.

Optimal: sort, then two pointers

In a sorted array, fix the smallest value a[i] and find pairs summing to -a[i] in the rest with two pointers, as in a sorted Two Sum: if the sum is too small, move lo right; if too large, move hi left.

Duplicates are skipped at the source instead of being removed afterwards:

skip an i whose value equals the previous a[i]: it would find the same triplets;
after a match, move lo and hi past all copies of the values already used.

Java

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

public class Main {
    static List<List<Integer>> threeSum(int[] nums) {
        int[] a = nums.clone();
        Arrays.sort(a);
        int n = a.length;
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (a[i] > 0) break; // the smallest value is positive, so no sum can be 0
            if (i > 0 && a[i] == a[i - 1]) continue;
            int lo = i + 1;
            int hi = n - 1;
            while (lo < hi) {
                int sum = a[i] + a[lo] + a[hi];
                if (sum < 0) {
                    lo++;
                } else if (sum > 0) {
                    hi--;
                } else {
                    result.add(List.of(a[i], a[lo], a[hi]));
                    while (lo < hi && a[lo] == a[lo + 1]) lo++;
                    while (lo < hi && a[hi] == a[hi - 1]) hi--;
                    lo++;
                    hi--;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
        System.out.println(threeSum(new int[]{1, -2, 1, 0, 5}));
        System.out.println(threeSum(new int[]{0, 0, 0, 0}) + " " + threeSum(new int[]{1, 2}));
    }
}

Output

[[-1, -1, 2], [-1, 0, 1]]
[[-2, 1, 1]]
[[0, 0, 0]] []

Time: O(n²): O(n log n) for the sort, then a linear two-pointer scan for each i. Space: O(1) besides the sorted copy and the output.

Edge cases

Fewer than three elements: no triplets.
All zeros: exactly one triplet, [0, 0, 0].
Overflow: three int values near the limits can wrap around silently. Add in long if the input allows it, or use Math.addExact, which throws ArithmeticException on overflow.