Programming Interview Question / how to find if any two integers in an array sum to zero?

Question

Not a homework question, but a possible interview question...

1. Given an array of integers, write an algorithm that will check if the sum of any two is zero.
2. What is the Big O of this solution?

Looking for non brute force methods

Answer 1

Use a lookup table: Scan through the array, inserting all positive values into the table. If you encounter a negative value of the same magnitude (which you can easily lookup in the table); the sum of them will be zero. The lookup table can be a hashtable to conserve memory.

This solution should be O(N).

Pseudo code:

var table = new HashSet<int>();
var array = // your int array
foreach(int n in array)
{
     if ( !table.Contains(n) ) 
         table.Add(n);
     if ( table.Contains(n*-1) )
         // You found it.;
}

Answer 2

The hashtable solution others have mentioned is usually O(n), but it can also degenerate to O(n^2) in theory.

Here's a Theta(n log n) solution that never degenerates:

Sort the array (optimal quicksort, heap sort, merge sort are all Theta(n log n))
for i = 1, array.len - 1
    binary search for -array[i] in i+1, array.len

If your binary search ever returns true, then you can stop the algorithm and you have a solution.