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.

### Like this:

Like Loading...

*Related*

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!

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