I guess this can be a place where I document my computer science adventures as well. The title is rather apt.


Anyway, the other day I ran into the 3SUM problem, which is the following:

Given a set S of n integers, do any three elements in S sum to 0?

This problem is O(n^2), and the most intuitive solution is the correct one and the most efficient one possible (:o).

SOLUTION

Sum all possible pairs of integers in the set. This is complexity O(n^2). Hash these sums into a new hashtable of size n^2/2. Now, run through the array once more. At each value, check to see if its additive inverse is in the hash table. If yes, the answer is yes. If no, continue on until the end. This part is O(n), but overall the algorithm is O(n^2). :)


*An interesting fact: according to Wikipedia, “A problem is called 3SUM-hard if solving it in subquadratic time implies a subquadratic-time algorithm for 3SUM.”

  1. bitestream posted this