## hama 3 years ago How can I count the number of pairs that sum to 0 in an unsorted array in linear time? I could have it in order of n log (n) using binary search, but I want to make it even faster than that.

1. agdgdgdgwngo

see if you can make some assumption on the data (are the elements all unique? Are the values of the elements as large as the size of the array?)

2. hama

They're not necessarily unique and they can be smaller or larger than the size of the array, just random numbers. But I don't see how that makes any difference in the algorithm!

3. shandelman

I think I've come up with a solution in Python using hash tables (the dictionary type specifically) since lookup time on hash tables is very very fast. Basically, the function walks through the list, and for every number x, it checks if -x is in the hash table. If it's not, it adds x to the hash table, and if it is, it increases the count and deletes -x from the hashtable. I keep increasing the number of numbers by a factor of ten and the time keeps increasing by a factor of ten, so, yeah...linear.

4. shandelman

Actually, whoops, this doesn't quite work for inputs such as [-5,-5,-5,5,5,5] because it will just return 1...hmm...

5. shandelman

Okay, the problem I introduced can easily be fixed by putting the number into the hash table and giving it the value of its count. So, the first time it sees a 5, it will put the key 5 and value 1 into the dictionary, and every other time it sees a 5, it will add 1 to its value. Then, when it sees its counterpart -5, it will decrement 5's value until it reaches zero, where it deletes it from the dictionary. A little flub on my part, but not too bad of a fix.

6. shandelman

(And this is why we come up with good test cases before tackling a problem, by the way. Heh heh.)

7. hama

I'll try that. Thanks!