## [f]izzbuzzer

### 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 {
}
}
}

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 });
}

}