@piyush could you give link to the actual problem ? couldn't understand - case 1. you are given just the set S, then how are you building this matrix ? case 2. you are given set A and B, then you can just sort and sum up and return results in O(n)
On Sat, Jul 9, 2011 at 10:59 PM, sunny agrawal <[email protected]>wrote: > i have an O(nlgn) solution in mind using O(n^2) memory > > All the values can be thought as the following matrix > (a0+b0) (a0+b1) (a0+b2).................................(a0+bn-1) > (a1+b0) (a1+b1) (a1+b2).................................(a1+bn-1) > . . > . . > . . > . . > . . > . . > . . > (an-1+b0) (an-1+b1) (an-1+b2)......................(an-1+bn-1) > > now as we can see all the rows and columns are sorted..... > now i will refer (ai,bj) as (i,j) > make a heap > insert (0,0) in heap > > now do the following n times > extract a pair value (i,j) > and insert (i+1,j) and (i,j+1) in heap not inserted > > TC : O(nlgn) > SC: O(n^2) to take care of already present elements in the heap > > > > > On Sat, Jul 9, 2011 at 4:54 AM, Piyush Sinha <[email protected]>wrote: > >> Given two sorted positive integer arrays A(n) and B(n). 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. >> >> >> -- >> *Piyush Sinha* >> *IIIT, Allahabad* >> *+91-8792136657* >> *+91-7483122727* >> *https://www.facebook.com/profile.php?id=100000655377926 * >> >> -- >> 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]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > Sunny Aggrawal > B-Tech IV year,CSI > Indian Institute Of Technology,Roorkee > > > -- > 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]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- 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]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
