Given an array, such as [1, 0, -1, 2, 3, 4, 5], find all subsets of length three where one element is equal to the sum of the other two elements in the subset. For example:
1 + -1 == 0 (from [1, 0, -1])
2 + 3 == 5 (from [2, 3, 5])
I came up with an O(n²) solution, but my interviewer insisted that there is an O(n log n) solution.
What is the best way to approach this problem?
At first glance, I can't see an algorithm that is less than O(n²). (Unless it is an extra-ordinarily clever one)
This problem is very similar to the infamous 3SUM question: Basically, the idea is that given a set of n elements, are there any triples that sum to zero?
An algorithm solving 3SUM faster than O(n²) is not known - This is an open problem in computer science... (See here: http://en.wikipedia.org/wiki/3SUM)
However, since your question is not exactly 3SUM (A+B+C=0), rather it involves (A+B=C), we cannot immediately preclude clever tricks (but we do make them very unlikely).
That being said, your problem can be transformed into A+B-C=0, which seems to me that such a solution would solve 3SUM in less than O(n²) as well...
Consider a solution to the 2SUM problem (that is, finding 2 element lists that sum to a certain value). We can Hash every element in the array (or some other data type with constant time lookup). Inserting every element takes O(n) time. This is the linear solution to a 2SUM problem. (One then loops over every element in the array and checks the hash for T-element)
Taking this idea, we can hash every sum in the array. However, getting every possible combination takes n*(n-1) or O(n²) time at best.
O(n²) I will be forever in awe of your number-fu (and if I find one, I will edit this and eat my words).
Good Luck in your search!
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments