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:

Approach: Sorting

Time Complexity: O(n^2)

Code:

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:

Output:

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

1 Response

  1. Sachin J Magdum says:

    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

Leave a Reply

Your email address will not be published. Required fields are marked *

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

%d bloggers like this: