Find three elements in an array that sum to a zero.

Objec­tive:  Given an array of integers write an algorithm to find 3 elements that sum to a zero. In short a+b+c = 0.

Example

int [] = { 3,-1,-7,-4,-5,9,10};
Elements are -4 9 -5

Approach: Brute Force

Use 3 nested loops and find the 3 elements which sum to 0.

Time Complexity: O(n^3)

Code:

public class ThreeNumbersSumZeroBruteForce {
public static void find(int [] a){
for (int i = 0; i <a.length ; i++) {
for (int j = i+1; j <a.length ; j++) {
for (int l = j+1; l <a.length ; l++) {
if(a[i]+a[j]+a[l]==0){
System.out.println("Found 3 elements whose sum is = 0");
System.out.println("Elements are " + a[i] + " " + a[j]+ " " + a[l]);
return;
}
}
}
}
System.out.println("Did not find 3 elements whose sum is = 0");
}
public static void main(String[] args) {
int a [] = { 3,1,7,4,5,9,10};
find(a);
}
}

Approach: Sorting

Time Complexity: O(n^2)

Code:

import java.util.Arrays;
public class ThreeNumbersSumZeroSorting {
//need to find a + b + c = 0
//OR we can reduce the problem to b + c = -a
public static void find(int [] x){
Arrays.sort(x);
for (int i = 0; i <x.length ; i++) {
int a = x[i];
//now problem is reduced to find two numbers in an array whose sum = -a
int sum = a;
int start = i + 1;
int end = x.length1;
while(start<end){
int tempSum = x[start] + x[end];
if(tempSum==sum){
System.out.println("Found 3 elements whose sum is = 0");
System.out.println("Elements are " + a + " " + x[start]+ " " + x[end]);
return;
}else if(tempSum<sum)
start++;
else //tempSum>sum
end;
}
}
}
public static void main(String[] args) {
int a [] = { 3,1,7,4,5,9,10};
find(a);
}
}

Approach: Use Hashing

  • Use the other loop to fix the one element at a time.
  • Now required_sum is (with two elements) = -fixed element.
  • Create a HashSet, Iterate through the rest of the array.
  • For current_element, remain_value = required_sum – current_element.
  • Check if remain_value in the HashSet, we have found our triplets else add current_element to the HashSet.

Time Complexity: O(n^2)

Code:

import java.util.HashSet;
public class ThreeNumbersSumZeroHashing {
//we need to find a + b + c = 0
//OR reduce the problem c = -(a+b)
public static void find(int [] x){
for (int i = 0; i <x.length ; i++) {
int a = x[i];
HashSet<Integer> set = new HashSet<Integer>();
for (int j=i+1; j<x.length; j++) {
int b = x[j];
int c = (a+b);
if(set.contains(c)){
System.out.println("Found 3 elements whose sum is = 0");
System.out.println("Elements are " + a + " " + b + " " + c);
return;
}else
set.add(b);
}
}
}
public static void main(String[] args) {
int a [] = { 3,1,7,4,5,9,10};
find(a);
}
}

Output:

Found 3 elements whose sum is = 0
Elements are -4 9 -5

1 thought on “Find three elements in an array that sum to a zero.”

  1. Improvement 1:
    Loop at line number 8 can be improved to execute till i < x.length – 1

    Improvement 2:
    Return statement at line number 18 should be removed to find other possible triplets in the array

    Reply

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.