I propose another solution with O(N LogN) Time Complexity and O(N^2) Space complexity (not sure if it would count towards space or time)
Space 1) Generate all possible combinations of A[i] + B[j] and maintain them in an array D (N^2 array) ---> O(N^2) 2) Build a min or max heap out of D array using bottom up building ---> O(N^2) Now D contains all possible sums of A[i] and B[j] in heap formation and the maximum height of the heap is O( Log N^2) = O(Log N) Time 1) For each C[k] search for -C[k] in the D heap. Search takes time atmost the height of the heap ---> O(N Log N) Please correct me if I'm wrong. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
