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 kth 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]}.