Given 2 dimensional sorted array(Both row and column wise sorted) write a efficient code to find median. asked 30 Jun '12, 18:55

The problem can be solved in a linear O(N) time ,where N is the Dimension of Matrix ,[if the matrix is Non Square Matrix ,then N=max (row,col)]. The Matrix in which Every row and Every columns are sorted is called YOUNG TABLEAU. This 2 D matrix or Tableau behaves as a Heap from one End and Binary search Tree from another End. This blog explains the approach ::
answered 30 Jun '12, 23:02

where "a" and "b" are 2 sorted arrays and n is size.. i hope this may help :) answered 30 Jun '12, 20:25

we can also do this by heap 
2a. now remove the min element & check its column number and insert into heap the next number from the same column like matrix[removedelementrow+1][removedelementcolumn] will be the new element .. insert it 2b. call min heapify on root 3.return the last extracted root answered 03 Jul '15, 02:58
