Algorithm I, Part I — 3 SUM

Q: 3-SUM in quadratic time. Design an algorithm for the 3-SUM problem that takes time proportional to N^2 in the worst case. You may assume that you can sort the N integers in time proportional to N^2 or better.

Quoting from Wikipedia: “In computational complexity theory, the 3SUM problem asks if a given set of n integers, each with absolute value bounded by some polynomial in n, contains three elements that sum to zero.” Suppose we have the following array [1, -9, 21, 2, 4, -5, -7, 10, 6, -8, -2, 0], we need to find all sets of integers (a, b, c) from the array such that a+b+c = 0

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

For each pair of a and b, we are trying to find if c = -(a+b) exists in the array. So to pair a and b, that is O(N^2). And to find c in the array, with linear search is O(N). In total it is O(N^3). This is the brutal force algorithm.

How can we improve? Or we should ask where we can improve: Either the pairing of a and b or the search for c.

For the search for c, it costs O(N) time. We can only improve it to O(logN) or O(1) time.

  • What search algorithm takes O(logN)? Well binary search does but it works on a sorted array.  So we sort the array first with MergeSort, which takes O(NlogN) time. Then in total we get O(N^2) * O(logN) + O(NlogN) = O(N^2logN), pairing of a and b times binary-search for c plus the sorting. So it is better, but not enough.
  • What search algorithm takes O(1)? Eh, none? Maybe we are constraining ourselves too much. It does not have to be a “famous algorithm” out there. Consider the following question: can we use some help, like additional data structure? If we can, what data structure helps you find something in O(1) time? Hashtable. So we need a hashtable to save all the integers and problem solved.
  • What if we cannot use additional data structure? Well for this one I didn’t figure it out so I peek at Wiki…They got a clever algorithm. I guess that part of my brain is just not wired to come up with the following idea. There are 3 cases: a + b + c = 0, > 0, and < 0.

Code on github:


Enhanced by Zemanta