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 */
Code WorkOut of the Day -- Daily exercises for programmers looking for jobs, or just to keep sharp with skills and have fun. I give talks, like this: https://youtu.be/NpvTE7GlXSM for people looking for jobs, or groups of programmers preparing for M&A tech HR due diligence. Follow us on twitter: @codewod
How to
When solving these problems, learning by doing is much better than learning by reading. I encourage to you read only as far in the solution as you need, then trying to solve the problem. If you get stuck, try reading a little further. And of course, let me know if you find a better solution!
your program return false if the array is [7, -3, 1, 10, 2]. you don't need two for loops, the hashtable already include sum for PAIRS, so you just need to find the third element.
ReplyDeletefunction findthreesum(int[] array)
{
if(arraylength < 3)
return false
for(int I=0; I<arraylength; I++)
{
if(hashtable.containskey(-array[I])
return true;
break;
}
}
Another solution if you want to use only constant additional space is to sort the array, calculate the pairwise sums and then do a binary search for the opposite value (rather than a lookup from the hashtable). This is O((n^2)logn) runtime, O(1) space.
ReplyDelete