×

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

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

 4 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  answered 30 Jun '12, 23:02 3.7k●4●25●49 accept rate: 27%
 1  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 :) answered 30 Jun '12, 20:25 619●2●8●13 accept rate: 10% 3.7k●4●25●49
 0 we can also do this by heap - creating min heap and keep the row and column also struct heap { int val, row , col }*h; 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 answered 03 Jul '15, 02:58 1★snehil92 95●2●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×138
×92
×74
×39

question asked: 30 Jun '12, 18:55

question was seen: 9,826 times

last updated: 03 Jul '15, 03:01