Objective : Given an array of integer write an algorithm to find 3 elements that sum to a zero. In short a+b+c = 0.

Example

int a [] = { 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: Run Code

Approach: Sorting

Sort the array.
Use the other loop to fix the one element at a time, say its ‘a’.
Now problem is reduced to “Find a pair of numbers from an array whose sum equals -a”
Time Complexity: O(n^2)

Code: Run 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 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 : Run Code

Output :

Found 3 elements whose sum is = 0
Elements are -4 9 -5
__________________________________________________
Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

Like this: Like Loading...

Related