Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Find three elements in an array that sum to a zero.

Objec­tive:  Given an array of inte­ger write an algo­rithm to find 3 ele­ments that sum to a zero. In short a+b+c = 0.

Exam­ple

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 ele­ments which sum to 0.

Time Com­plex­ity: O(n^3)

Code:

Approach: Sort­ing

  • Sort the array.
  • Use the other loop to fix the one ele­ment at a time, say its ‘a’.
  • Now prob­lem is reduced to “Find a pair of num­bers from an array whose sum equals –a”

Time Com­plex­ity: O(n^2)

Code:

Approach: Use Hashing

  • Use the other loop to fix the one ele­ment at a time.
  • Now required_sum is (with two ele­ments) = –fixed element.
  • Cre­ate a Hash­Set, Iter­ate through rest of the array.
  • For current_element, remain_value = required_sum – current_element.
  • Check if remain_value in the Hash­Set, we have found our triplets else add current_element to the hashset.

Time Com­plex­ity: O(n^2)

Code:

Out­put:

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

You may also like...