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 <ecstasy.piy...@gmail.com>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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
