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

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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