Thursday, October 27, 2011

Find the Kth (smallest) Pair from the Elements in Two Sorted Arrays

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 kth smallest pair. The complexity is  O(k*log(n+m)).

2 comments:

  1. one doubt...

    as 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

    ReplyDelete
    Replies
    1. {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.

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

      Delete