Given an array of integers and an integer S, find if there are two numbers X and Y in the array such that X + Y = S. The problem was received by a friend during a phone interview with Google. A naive solution is:

void solutionNaive(vector& inVals, int sum) //O(n^2)
{
size_t size = inVals.size();
//naive
for (int i = 0; i < size-1; i++)
{
for (int j = i+1; j < size; j++ )
{
if (inVals[i] + inVals[j] == sum)
{
printf("Values: %d and %d\n", inVals[i], inVals[j]);
return;
}
}
}
printf("Not found\n");
}

This is and its performance definitely not acceptable for large arrays. A faster solution is to use a hash set for storing the elements tested so far, and to test if S minus the current element was already stored in the hash set. More memory is used in this approach, but the complexity in this case is because searching in a hash set or hash map is :

void solutionOk(vector& inVals, int sum) //O(n)
{
hash_set checkedVals;
for (vector::iterator it = inVals.begin(); it!= inVals.end(); ++it)
{
if (checkedVals.find(sum - (*it)) != checkedVals.end())
{
printf("Values: %d and %d\n", sum - (*it), *it);
return;
}
else
{
checkedVals.insert(*it);
}
}
printf("Not found\n");
}

An other possible solution, not so efficient but interesting, is to sort te numbers and then for each X in the array to use binary search for searching if S-X is there. The complexity is , and no additional memory is used. An important aspect of this method is the way it handles the case when S-X = X:

void solutionNotSoBad(vector& inVals, int sum) ////O(n log(n))
{
size_t size = inVals.size();
//sorting is O(n log(n))
sort(inVals.begin(), inVals.end());
bool found = false;
for (vector::iterator it = inVals.begin(); it != inVals.end(); ++it)
{
vector::iterator current = it;
int toFind = sum - (*it);
if ((toFind <= *it) && (it!= inVals.begin()))
{
found = binary_search(inVals.begin(), --current, toFind);
current = it;
}
if ((toFind >= *it) && (it != inVals.end()))
{
found = binary_search(++current, inVals.end(), toFind);
current = it;
}
if (found)
{
printf("Values: %d and %d\n", (*it), toFind);
return;
}
}
printf("Not found\n");
}

As a conclusion, keep in mind that hash based data structures are generally the most appropriate to use when fast search operations are needed.

### Like this:

Like Loading...

*Related*

Hi. You might want hyperlink what hash based structures are… Helpful post nonetheless 🙂