Let S(k) indicate the kth largest sum as per the question. We can also say that every S corresponds to a pair, (u,v) such that S=a[u]+b[v].
Now the idea is to keep track of two previous S's (in turn two pairs) such that one pair has the greatest 'u' of all so-far pairs. That is, this pair has most advanced on array a. And the other has the highest 'v' of all. This pair has advanced most on array b. Sometimes the same pair may top in both u and v. Then finding the next S would be simple. Assume we are to find S( j ), and that S(h) and S(i), where h,i < j < k, have advanced most on array a and b respectively. If S(h)= a[p]+b[q] and S(i)= a[r]+b[s], then obviously p >= r and q >=s, and we have four candidate pairs for S(j): (p,q+1), (p+1,q), (r,s+1) and (r+1,s). Now S(j) is calculated as S(j)= max( a[p]+b[q+1], a[p+1]+b[q], a[r]+b[s+1], a[r+1]+b[s] ). We should update S(h) and S(i) based on which of these is maximum. Complexity is in O(m+n) i think. On Wed, Oct 6, 2010 at 4:04 PM, sourav <souravs...@gmail.com> wrote: > you are given 2 arrays sorted in decreasing order of size m and n > respectively. > > Input: a number k <= m*n and >= 1 > > Output: the kth largest sum(a+b) possible. where > a (any element from array 1) > b (any element from array 2) > > The Brute force approach will take O(n*n). can anyone find a better > logic. thnkx in advance. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 algoge...@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.
