CareerCup

Suppose C is the smallest array. Sort A and B, and for each element x in C, do the usual algorithm to find x in the implicit 2D array [Sij] where Sij = Ai + Bj.

No one knows how to do (much) better without some restrictions on the input.

I guess solution might come from Dynammic programming.That might reduce the o(n^3) complexity of brute force algo into somethings less.

A O(n^2) complexity could be:

1. Convert array A to Hash Table
2. For any pair of element c in C and b in B, find if -(b+c) is in the hash table.

Not very if lower compexity solution could be found or not

sort A,B,C, then modifying merge sorted to search for A_i+B_j+C_k. Time O(nlogn) , n is the length of A or B or C

A solution with O(n) complexity.

Create a hash table, that contain all the possible sum combination of any of the 2 list.

A X B

A[1] + B[1....n]
A[2] + B[1....n]
...
...
A[n] + B[1....n]


Its a one time effort with O(n*n).

And it provide lateral access & solution with O(n).

Check if -(C[index]) exists in the hash table then return true.

I can think of only hash as a sol can anybody give better solution

When you mention a hash table mention the hash key and hash function because hash table is nothing without it.And only with that detail we can determine the worst case complexity of the solution.

for each of n*n element combination from A&B build a binary search tree. Building a tree takes O(N) where N = n*n.

then for each of n elements from C, Do a binary search on the tree which is expected to be O(nLgn) thus the Overall complexity of the solution remains O(n^2)

First sort all of them (O(nlogn) complexity)
A -> ascending
B & C -> descending

Now to make understanding simpler,lets take an example

A=> -4 -1 3 6 7 8 i

B=> 9 7 3 2 1 -5 -6 j

C=> 12 5 2 1 0 -1 -5 k

LOOP { // exit if i+j+k == 3n
1.check if A[i] + B[j] + C[k] ==0,if yes return true;

2. if not then if A[i] + B[j] + C[k] <0
i = i + 1
3. else {
if(A[i] + B[j+1] + C[k] == 0) return true;
if(A[i] + B[j] + C[k+1] == 0) return true;
j = j+1;
k = k+1;
}
END LOOP

The idea is to
=> if sum < 0 ,then value at A should be increased to get zero so i is incremented
=> if sum > 0 ,then B and C should be decreased to get zero so j and k is incremented.

Complexity = sorting + interation
= o(nlogn) + O(3n)
= O(nlogn)

pls note :- Just for sake of understanding,i have taken i,j,k;They can be implemented using ->next in a linked list.

Guys,ur comments are welcome!

3SUM-Hard problem. Look it up and stop wasting everyone's time with sub-quadratic solutions.

My algorithm would do...
minA = lowest element in A (On).
minB = lowest element in B (On)
minC = lowest element in C (On).
if minA + minB + minC > 0 => return false
else return true.
This would be On overall.

I think this would solve the problem. Or am i crazy?

Thanks.

Ooops yes i think i am crazy too. Sorry, i misunderstood the problem. I thought it could be <= 0. That would be too easy :)

can anybody give foolproof ans

you guys are so funny! I have some rough idea of O(n^2) complexity.
first construct hashtable for numbers in B and C, setup flag indicating which list each number belongs. like this
Hashtable:
key value
number B or C or BC

then iterate each number in A, suppose the value of one number is m
then you need to find the sum of numbers from B and C which sums to -m
do linear search in hashtable. it can be done in O(n) since number value
is the key of hashtable.

you guys are so funny! I have some rough idea of O(n^2) complexity.
first construct hashtable for numbers in B and C, setup flag indicating which list each number belongs. like this
Hashtable:
key value
number B or C or BC

then iterate each number in A, suppose the value of one number is m
then you need to find the sum of numbers from B and C which sums to -m
do linear search in hashtable. it can be done in O(n) since number value
is the key of hashtable.

U can do it in O(n^2 log n)
Sort C. Now for each pair of (a,b) binary search to see if the required c exist.

{
Sort B, C

for all A[i]
{
j=0;
k=n-1;
while(j<k)
{
if B[j] + C[k] < - A[i]
j++
else if B[j] + C[k] > - A[i]
k--;
else return true
}

}

return false
}

This becomes more interesting if -ve numbs are allowed in the input.
Use 3 min-heaps for each of the lists. And check whether the topmost elements sums up to 0.
P.S: this works only if the arrays are sorted, if not you should heapify at the start O(nlogn).

@arvind646 : ya ur sollution is right really fine using the heap and maiontaining the sum as variable always 3 member be there at the heap and its so easy time coplexity over all that is taking sorting as werll be nlgn a really gud slution means we are taking sme extra space that is constant too means heap will always be of size 3 :)