use pointers and lengths of two arrays. depends on what K is, if K> m*n/2, you reverse the pointers. therefore, the worst case is either O(m) when length of m is shorter or O(n) when length of n is shorter,
make the pointers pointing to the first elements in both arrays. A) 4,3,2,2,1 ^ B) 5,3,2,1 ^ compare them to find out which one is larger, here 5 is larger than 4. by definition, you know 5 would be bigger than any elements in array A, and sum of 5 with kth element of array A (here, kth <= A.length) will be the one(kth largest sum(a+b) overall) you are looking for. if k>A.length, shift the pointer of B one number to the right and repeat the same process. like i said, if the k> m*n/2, start from small On Oct 6, 6:34 am, 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
