Find kth Element in bi-directional Sorted Array

Posted: August 23, 2012 in Uncategorized

Q. You are given a 2D array sorted horizontally as well as vertically. Find kth smallest element.

A. Maintain a min heap of size n. A location pointer will be maintained for checked elements in each row.

Drop 1st element from each row, move the location pointer then 2nd row.

Pull out the minimum element, note the row from which it belonged and put the next element from the same row in the heap.

Repeat the process K times. Kth smallest element will occur at that stage.

 

Advertisements
Comments
  1. lkshminarayanan says:

    if the array is sorted both horizontally and vertically, wouldn’t be the first element any row always the minimum??.. in any row i, a[i][0] < a[i][2]< a[i][2]…< a[i][n]..??.
    Generally for any i and j, a[i-x][j-y] will always be less thean a[i][j]. So pulling out the minimum element in the third step doesn't make sense!

    • Harsh says:

      k can be more than the length of the array. Hence, its not necessary that at a given point, we are operating only over a single row/column.
      a[i][0] < a[i][1]. But, at next step, once a[i][0] is out, same equation cannot be applied to – a[i+1][0] & a[i][1].

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s