Sunday, October 27, 2013

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(n3) 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.
This procedure takes O(n log n) for sorting the array and O(n2) for actually finding the triplet. So the overall time complexity would be O(n2) and O(1) extra space. 

Here is the java code to do this.