Java implementation of median of Row wise Sorted Matrix

Problem Statement

Given a matrix of size N*M,also the matrix is sorted row wise & the total number of elements in the matrix is guaranteed to be odd.Find the median of the matrix.

Example:

input:N=3,M=3

     1, 3, 5 

     2, 6, 9   

     3, 6, 9

output: 5

Explanation: Single array representation is [1,2,3,3,5,6,6,9,9],median =5

 input:

            N=3,M=1

            1

            2

            3 

output: 2 

Approach: Create an Min-Heap and insert first elements of every row along with its row number and column number in min heap.Now remove smallest element from min heap and add its corresponding next row value, row number and column number in the min heap.(N*M + 1) / 2 removal will be the median of the row wise sorted matrix. 

Solution

Below is the Java implementation of the above approach

Code

class Solution {
    public static int median(int mat[][], int r, int c) {
        int n=r;
        int k=(int)Math.ceil((double)r*c/(double)2);
        if(k<0 && k>=r*c)
        {
            return -1;
        }
        PriorityQueue<triplet> minheap=new PriorityQueue<>();
        for(int i=0;i<n;i++)
        {
             triplet tr=new triplet(mat[i][0],i,0);
             minheap.add(tr);
        }
        while(k>1)
        {
            triplet tr=minheap.remove();
            int x=tr.x;
            int y=tr.y;
            if(y+1==c)
            {
                triplet tt=new triplet(Integer.MAX_VALUE,-1,-1);
                minheap.add(tt);
            }
            else
            {
                triplet tt=new triplet(mat[x][y+1],x,y+1);
                minheap.add(tt);
            }
            
            k--;
        }
        triplet tr=minheap.remove();
        return tr.data;     
    }

    public static void main(String [] args)
    {
        int n=3,m=3;
        int mat[][]={{1,3,5},
                     {2,6,9},
                     {3,6,9}};
        System.out.println(median(mat,n,m));
                    
            
    }
}
class triplet implements Comparable<triplet>{
    int data;
    int x;
    int y;
    triplet(int data,int x,int y)
    {
        this.data=data;
        this.x=x;
        this.y=y;
    }
    @Override
    public int compareTo(triplet o) {
        return this.data-o.data;
    }

} 

output: 

5 

Feel free to comment if you have any doubt in comments section

For more Data structure and algorithms,computer science,programming,coding related problems search my website

Learn how to prepare for Information Technology Based companies here