Another very frequently-visited problem is "The 3SUM Problem", sometimes also known as the Subset Sum Problem This problem lays path to many concepts in Algorithmic Science such as sub-quadratic time problems, 3SUM hard problems, etc.
INPUT :
A sequence (taken in as an array A) of n distinct integers, preferably whose absolute value (modulus) can be given by a polynomial p(n).
OUTPUT :
The combinations of 3 integers from the sequence whose sum equals 0 i.e. the numbers i, j and k such that i+j+k = 0. Note that the integers i, j, k have to be distinct and the combinations themselves have to be distinct. For example, i,j,k and k,j,i represent the same combination and therefore, are not distinct.
THE "BRUTE FORCE" METHOD :
The obvious and perhaps the most trivial method would be to scan the array 3 times in one direction (to ensure distinctness of the combinations) and take every possible combination of 3 integers and check whether their sum is 0. For an n-input array, the number of combinations will be nC3 = O(n3). The following algorithm is an illustration of the above method.
Algorithm 3SUM (A, n)
THE BINARY-SEARCH METHOD :
This method uses the idea that instead of traversing the array for 3 elements requiring 3 nested for loops, we can traverse the array only 2 times using the following simple manipulation:
if x+y+z = 0, then z = - (x+y)
Thus, if we choose a particular "x" and a "y", we just need to search the array for the "z". This searching can be done by an efficient search technique, The Binary Search Technique. This technique, however requires us to first sort the array, hence that will be our first step.
We assume a routine binarySearch(Array, low, high, key) which searches for "key" within the bounds "low" and "high" and returns the index of the key, if found or if not found; returns -1.
Algorithm 3SUM PLUS (A, n)
THE HASH MAP METHOD :
We continue with the above idea of traversing the array only twice instead of 3 times. We will prove later that the sorting technique used doesn't play a role in the final performance, so the only scope of improvement is in the search technique. We need a search technique faster than the Binary Search. Hash-based searching is an example. Searches performed using a hash table take O(1) if we know the hash index or the function that gives the hash index. Therefore, we will copy the entire array into a hash table and then inside the nested for loop, we search the hash table for the integer z = - (x+y).
Algorithm 3SUM PLUS PLUS (A, n)
INPUT :
A sequence (taken in as an array A) of n distinct integers, preferably whose absolute value (modulus) can be given by a polynomial p(n).
OUTPUT :
The combinations of 3 integers from the sequence whose sum equals 0 i.e. the numbers i, j and k such that i+j+k = 0. Note that the integers i, j, k have to be distinct and the combinations themselves have to be distinct. For example, i,j,k and k,j,i represent the same combination and therefore, are not distinct.
THE "BRUTE FORCE" METHOD :
The obvious and perhaps the most trivial method would be to scan the array 3 times in one direction (to ensure distinctness of the combinations) and take every possible combination of 3 integers and check whether their sum is 0. For an n-input array, the number of combinations will be nC3 = O(n3). The following algorithm is an illustration of the above method.
Algorithm 3SUM (A, n)
- for i = 0 upto (n-2)
- for j = i+1 upto (n-1)
- for k = j+1 upto n
- if (A[i] + A[j] + A[k] == 0) then print A[i], A[j], A[k]
THE BINARY-SEARCH METHOD :
This method uses the idea that instead of traversing the array for 3 elements requiring 3 nested for loops, we can traverse the array only 2 times using the following simple manipulation:
if x+y+z = 0, then z = - (x+y)
Thus, if we choose a particular "x" and a "y", we just need to search the array for the "z". This searching can be done by an efficient search technique, The Binary Search Technique. This technique, however requires us to first sort the array, hence that will be our first step.
We assume a routine binarySearch(Array, low, high, key) which searches for "key" within the bounds "low" and "high" and returns the index of the key, if found or if not found; returns -1.
Algorithm 3SUM PLUS (A, n)
- sort(A)
- for i = 0 upto n
- for j = i+1 upto (n-1)
- k = binarySearch(A, j, n, -(A[i] + A[j]) )
- if(k != -1) then print A[i], A[j], k
THE HASH MAP METHOD :
We continue with the above idea of traversing the array only twice instead of 3 times. We will prove later that the sorting technique used doesn't play a role in the final performance, so the only scope of improvement is in the search technique. We need a search technique faster than the Binary Search. Hash-based searching is an example. Searches performed using a hash table take O(1) if we know the hash index or the function that gives the hash index. Therefore, we will copy the entire array into a hash table and then inside the nested for loop, we search the hash table for the integer z = - (x+y).
Algorithm 3SUM PLUS PLUS (A, n)
- sort(A)
- for i = 0 upto n
- hash.put(<unique key determined by a hash function>, A[i])
- for ends
- for i = 0 upto n
- for j = i+1 upto (n-1)
- k = hash.search(- (A[i] + A[j]) )
- if (k != null) then print A[i], A[j], k
- nested for ends
Wikipedia offers another interesting method which also gives O(n2) but does not use hash tables. Go, have a look here
FUN FACT : Although it hasn't been successfully proved that the 3SUM problem can't be solved faster than O(n2), no better algorithm has yet been found. Do you have it in you to find it? Leave us a comment!
No comments:
Post a Comment