November 29th, 2013, 09:07 AM
A better algorithm
Sorry if this question has been asked before but I need some help on this as I am stuck on this for more than one year. The problem is as follows -
I have three arrays A,B,C of same size let say n and I need to find out all possible (i,j,k) such that A[i]+B[j]=C[k]. And we
need to find this in O(n^2) complexity for which I found one solution like
Add all A[i]+B[j] as the key and (i,j) as values in a hash table.This gives n^2 no of keys and values.
Traverse for all C[k] and probe the hash table.If mach found (i,j,k) is one pair and so on.
This looks like an O(n^2) solution.But can it be done better or at least O(n^2) in some different approach ?
Tags for this Thread
Click Here to Expand Forum to Full Width
This is a CodeGuru survey question.