Problem solving with programming: Finding three elements with zero sum in an array.

Problem solving with programming: Finding three elements with zero sum in an array.

Given an array of positive and negative numbers, how do we write a program to check if it has three elements with sum 0.

For example, the array  {-31, 19, -6, -45, 12, -8, 3, -77, 56, 29} contains {-31,12,19} with sum zero.

One obvious solution is to examine each possible triplet of the array and check if there is a triplet with sum = 0. But this takes O(n³) time and is not efficient for large arrays.

A better approach would be to sort the array first in increasing order. Follow this iterative algorithm.

• Fix the first element, start two pointers one at the begin and the other at the end of the sorted array. 
• If the sum of the three elements is zero return.
• If the sum is greater than zero, we decrement the end pointer so that the sum moves closer to zero
• If the sum is negative, we increment the begin pointer to add up value to sum.
• Iterate this procedure until the fixed element moves towards the end.

Read full article from Problem solving with programming: Finding three elements with zero sum in an array.