Given two sorted postive integer arrays A(n) and B(n) (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. in O(n).

Any responses to this as I am not able to find out solution for it?

ReplyDeleteDo you have any solution for that? I am still stuck at O(n log n) using a heap.

ReplyDeleteEssentially, you have n sorted lists, each of which is indexed by the first component of the sum, and you want to merge them to find out the largest (or smallest, whatever) n. So I don't see how you can break O(n log n) unless you drop the

comparison model assumption.

I tried either to generate elements one at a time, or to implement randomized quickselect

trying to rewrite partition "blindly", but still

no luck.

but the list are already sorted, don't forget it. is this that alessio?

ReplyDeleteI see.. however my question still stands. The first element (the largest) of the output array is the biggest element among the ending ones in the lists.

ReplyDeleteYou extract that, and you go on. If you do that with a heap you have a O(n log n) algorithm. And I don't think that it can be beaten so easily.

Where am I seeing this wrong?

dynamic programming, with some additional observation -- giuseppe

ReplyDelete