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

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.

 public class ThreeNumbersSumZeroBruteForce { public static void find(int [] a){ for (int i = 0; i

Approach: Sorting

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.

 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 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.

 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 set = new HashSet(); for (int j=i+1; j

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