You are not logged in. Please login at www.codechef.com to post your questions!

×

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

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

asked 30 Jun '12, 18:55

innocent_avi's gravatar image

2★innocent_avi
0113
accept rate: 0%

edited 30 Jun '12, 18:56


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
link

answered 30 Jun '12, 23:02

ritesh_gupta's gravatar image

5★ritesh_gupta ♦
3.7k42549
accept rate: 27%



        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 :)

link

answered 30 Jun '12, 20:25

shashank_jain's gravatar image

2★shashank_jain
6192813
accept rate: 10%

edited 30 Jun '12, 22:27

ritesh_gupta's gravatar image

5★ritesh_gupta ♦
3.7k42549

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

link

answered 03 Jul '15, 02:58

snehil92's gravatar image

1★snehil92
9522
accept rate: 0%

edited 03 Jul '15, 03:01

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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