Find triplets in an array such that the sum of two numbers is also a number in a given array
For an array such as [1, 0, -1, 2, 3, 4, 5]
, find all subsets of length three where one element is 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 a solution O(n²)
, but my interviewer insisted there was a solution O(n log n)
.
What is the best way to solve this problem?
source to share
At first glance, I don't see an algorithm that is smaller O(n²)
. (Unless it's unusually smart)
This problem is very similar to the infamous 3SUM question: Basically, the idea is that for a given set of n elements, are there three times that sum to zero?
Solving the 3SUM algorithm is faster than O(n²)
unknown - 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 includes ( A+B=C
), we cannot rule out smart tricks right away (but we make them very unlikely).
So your problem can be converted to A+B-C=0
, and it seems to me that such a solution would resolve 3SUM less than O(n²)
, and also ...
Consider this solution for such a task:
Consider solving the 2SUM problem (i.e. finding 2 lists of items that are summed to a specific value). We can display every item in the array (or some other persistent time-searched data type). Inserting each item takes time O(n)
. This is a linear solution to the 2SUM problem. (Then the loop iterates over each element of the array and checks the hash for T-element
)
Taking this idea, we can hash each sum in the array. However, getting every possible combination takes at best n*(n-1)
or O(n²)
.
If anyone has a solution faster than
O(n²)
that, I'll be forever in awe of your fu-number (and if I find one, I'll edit it and eat my words).
Good luck with your search!
source to share