Find Median in 2-d sorted array(sorted in both order column and row wise)?

general
, , ,
1

Given 2 dimensional sorted array(Both row and column wise sorted) write a efficient code to find median.

2

int median(int a[], int b[], int n)
{
int med1,med2;
if(a[n-1] < b[0])
return a[n-1];
if(b[n-1] < a[0])
return b[n-1];
if(n==2)
{
int c[4];
merge(a,b,c,2);
return c[1];
}
med1 = a[(n-1)/2];
med2 = b[(n-1)/2];
if(med1 == med2)
return med1;
else if(med1 < med 2)
return median(&a[(n-1)/2],b,n/2+1);
else
return median(a,&b[(n-1)/2],n/2+1);
}

where “a” and “b” are 2 sorted arrays and n is size…

i hope this may help :slight_smile:

1 Like
3

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
4 Likes
4

we can also do this by heap -

  1. creating min heap and keep the row and column also
    struct heap
    {
    int val, row , col
    }*h;

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