**Problem:**Given two sorted array, by choosing one element from each array we have a pair. A pair can be ranked by the sum of the two numbers within it. Find the Kth smallest pair.

**Solution:**Naive approach takes O(n*m). Here we can borrow the idea that is used to merge multiple arrays. Basically we need a heap or a priority-queue. The main idea is as follows:

- Put the first pair (which is definitely the smallest) {a[0], b[0]} in the heap as bootstrapping.
- Loop over the heap, if heap is not empty, pop the top of the heap {a[
*i*], b[*j*]}. If*i*<n-1, push {a[*i+1*], b[*j*]}; If*j*<m-1, push {a[*i*], b[*j+1*]}. - pop
*k*times we will get the*k*th smallest pair. The complexity is O(k*log(n+m)).

one doubt...

ReplyDeleteas mentioned in your post...

/*

pop the top of the heap {a[i], b[j]}. If i<n-1, push {a[i+1], b[j]}; If j<m-1, push {a[i], b[j+1]}.

*/

here pop means are you removing root node...???

bcoz you didnt push(a[i],b[j])...after adding

{a[i+1], b[j]} and {a[i], b[j+1]}.

actually there is no need of poping a[i],b[j]...which is nothing but a root node..i guesss

{a[i],b[j]} is already in the heap. After popping it (a.k.a, removing it from heap), we add {a[i+1], b[j]} and {a[i], b[j+1]} to the heap.

DeleteFor a min-heap, the root is the smallest element. You need to pop {a[i],b[j]}, otherwise if {a[i],b[j]} is still in heap, it will always remain as root. Then it is not efficient to get the next pair after {a[i],b[j]}.