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^{3}) 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(n^{2}) for actually finding the triplet. So the overall time complexity would be O(n^{2}) and O(1) extra space.

Here is the java code to do this.