Given 2 dimensional sorted array(Both row and column wise sorted) write a efficient code to find median.
int median(int a, int b, int n)
if(a[n-1] < b)
if(b[n-1] < a)
med1 = a[(n-1)/2];
med2 = b[(n-1)/2];
if(med1 == med2)
else if(med1 < med 2)
where “a” and “b” are 2 sorted arrays and n is size…
i hope this may help
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 ::
Lets name the matrix A of size N x N Take any element A[i][j] 1. A[i][j] < A[t][j] for t = i+1 ....... N 2. A[i][j] < A[i][t] for t = j+1 ....... N 3. A[i+1][j] and A[i][j+1] can be thought of as childs of A[i][j] thus above structure resembles a heap similarly from upper right corner the matrix looks like a BST do insert operation in BST --> O(n) in this case do search operation in HEAP --> O(n) in this case
we can also do this by heap -
creating min heap and keep the row and column also
int val, row , col
do following (n*n)/2 times
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