Given two sorted postive integer arrays A[n] and B[n] (W.L.O.G, let's say they are decreasingly sorted), we define a set S = {(a,b) | a \in A and b \in B}. Obviously there are n^2 elements in S. The value of such a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs from S with largest values. The tricky part is that we need an O(n) algorithm.
Logic:
Take the two arrays and Take a maximal heap...
Now add into heap the first element (A[0]+B[0])...
Now Remove the maximum from the heap...And Print i...
Now if the removed element was (A[i]+B[j]) then push (A[i+1]+B[j]) and (A[i]+B[j+1])...
Do this until you get n elements...
Answer Contributed by f2001840
2 comments:
i think the heapify algo has the worst case complexity of O(NlogN)
At any step A[i]+B[j], how do you know which element(i and j combination) have you removed? Do you want this book-keeping for every element in the heap?
Post a Comment