3 integers that sum to zero

Problem:  Given an unsorted array of integers, return true if there is a 3-element subset, of distinct elements, that sums to zero


bool threeSumToZero(int a[]){
...
}


Soution:  Well, there seems to be an obvious answer here.  We can iterate through the array and for each element, we iterate and then iterate again to check all three element combinations.  And, so long as we're careful and make sure that we use distinct elements, we can get this right.  


The code for this is:



bool threeSumToZero(int a[]){


    int i, j, k;


    for(i=0; i < a.length, i++) {
        for (j=0; j < a.length; j++) {
            for (k=0; k < a.length; k++) {
                //check for distinct elements
                if (i !=j && i != k && j!= k) {
                    if ((a[i] + a[j] + a[k]) == 0 ) 
                        return (true);
                }
            }
        }
    }
    return (false); 
}


Well, this works beautifully and is a very simple solution.  There are a few optimizations possible (like starting j at 1 and k at 2) and combining the two if statements, but basically this is pretty sound.  


What is the algorithmic run time for this?  


Well, since for each element, we check each element and then check each element for that, we  have an O(n) with another O(n) for each n and then another O(n) for each of those.  This results in a run time of O(n^3).


We could stop here, but O(n^3) is pretty slow.  So, let's think about a potential optimization. You may see an optimization, but if you don't, let's try an example:

Pic 1 shows an array that will sum to zero.  How do we know this.  Well, we can see that -3 + 2 + 1 = 0.


Now, how did we inuit this?  


What you probably did, was check the sums, and then see if there was a value which was opposite that (e.g., negative if the sum was positive, and positive if it was negative).  You didn't have to actually check the sum of each element, only the membership of the opposite of the sum.


This hints at the solution to make it faster.  Since we don't have to check all sums of triplets; we can just check the sum of every pair, and then see if there is an opposite.  And, since look up can be a constant time operation after we build a data structure with O(n) time, we can:


1.  Build a constant time lookup, like a hashtable, an O(n) operation
2.  Determine the sum of all pairs,  an O(n^2) operation, and
3.  Check if we have the opposite of the sum in a hash table, an O(1) operation


This will give us an O(n^2) algorithm, but at the tradeoff of needing a data structure.


The code for this is:

bool threeSumToZero(int a[]){


    int i, j;
    //assume we have hashtable functions:
    hash *h;
    
    h = buildHashTable(a);


    for(i=0; i < a.length, i++) {
        for (j=0; j < a.length; j++) {
            //check for distinct elements
            if (i !=j) {
                if (lookup(h, -(a[i] + a[j]))) 
                    return (true);
            }
        }
    }
    //you could free the hashtable here if needed
    return (false); 
}



Beautiful.  This is an example of an obvious solution being nice, but inefficient.  It's good to always get to a working solution fast.  Then, by doing an example and intuiting what we were doing, it's possible to build a much more efficient algorithm.  And, the coding isn't too difficult; it's mostly the algorithm here.


/*Please let me know if you find any bugs or have comments.  Thanks, Noah */