Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Zero-sum triplets challenge

Sharing is caring!

Problem statement
Given an array of distinct elements find all triplets in array whose sum is equal to 0.

Sample input

0, -1, 2, -3, 1

Sample output

0 -1 1
2 -3 1

Solution
We will solve this algorithm in \mathcal{O}(n^2) time using hashing. The first iteration will be over all elements of our array. Let that elements be a[i]. Then we sum each a[i] with a second element a[j] (nested loop) and check whether we have a third element x that is equal to -(a[i] + a[j]) in our HashSet because x + a[i] + a[j] would then be equal to 0. If no such element exists we add the current a[j] to the HashSet for future lookups and continue. For each iteration for elements a[i], we generate a new lookup HashSet.

Full Code

public class FindZeroSumTriplets {

    private static void pair(int i, int[] a) {
        int n = a.length;

        Set set = new HashSet();

        for (int j = i + 1; j < n; j++) {
            if (set.contains(-1 * (a[i] + a[j]))) {
                System.out.println(" (" + a[i] + ", " + (-1 * (a[i] + a[j])) + ", " + a[j] + ")");
                return;
            } else {
                set.add(a[j]);
            }
        }
    }

    private static void solve(int[] a) {
        int n = a.length;
        System.out.println("Solving for " + Arrays.toString(a));

        for (int i = 0; i < n; i++) {
            pair(i, a);
        }

        System.out.println();
    }

    public static void main(String[] args) {
        solve(new int[] { 0, -1, 2, -3, 1 });
        solve(new int[] { 1, -2, 1, 0, 5 });
        solve(new int[] { 0, 0, 0, 0 });
        solve(new int[] { -1, 2, -1, 3, -2 });
    }

}