**Objective**: 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**

- Sort the array.
- Use the other loop to fix the one element at a time, say its ‘a’.
- Now the problem is reduced to “Find a pair of numbers from an array whose sum equals to K“

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.length–1; | |

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

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