9. Kth smallest element in a row and column wise sorted Matrix

9. K^th smallest element in a row and column wise sorted Matrix

Problem link :- click here

package progams;

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;


class HeapElement implements Comparable<HeapElement>
{
	int row;
	int column;
	int value;
	
	HeapElement(int r, int c, int value)
	{
		this.row = r;
		this.column= c;
		this.value = value;
	}

	@Override
	public int compareTo(HeapElement o)
	{
		if(this.value == o.value)
			return 0;
		else if(this.value > o.value)
			return 1;
		else
			return -1;
	}
}

public class Matrix__9
{
	
	/*
	    Given a N x N matrix, where every row and column is sorted in non-decreasing order.
	    We have to find the kth smallest element in the matrix.
	    
	   				16    28    60    64
	   				22    41    63    91
	   				27    50    87    93
	   				36    78    87    94
	   				
	   	we take the first row in a priority queue. in the queue we have elements arranged in increasing order.
	   	so the first element of the queue will be the smallest element. We will poll() that element and 
	   	increment the counter to find the kth smallest.  
	   	we compare counter and the 'k' if they are equal we will return that element.
	   	if counter and 'k' are not equal then we will add()       the element below that element in that matrix.
	   		eg :- if we pool()    16  &  counter!=k     then     add()   22
	   		
	   	to do this operation we have to store the    row  and   column   along with the value.  
	   	Therefore we are going to create a class which can store all these things.
	   	NOTE :- we have to implement comparable      because we need a particular order in queue
	*/
	 
	static int kthSmallestElement(int mat[][], int r, int c, int k)
	{
		if(k  >  r*c-1)
			return -1;
		
		Queue<HeapElement> queue = new PriorityQueue<>();
		
		//adding all the elements of first row to the queue
		for(int i=0; i<c; i++)
		{
			queue.add(  new HeapElement( 0, i, mat[0][i] )   );
		}
		
		//polling the smallest elements one by one
		int count = 0;
		while(!queue.isEmpty())
		{
			HeapElement x = queue.poll();
			count++;
			
			//if count is the asked value then we will return that element
			if(count == k)
				return x.value;
			
			//if count doesn't matches the asked value then add the element below that polled element
			//we also need to check if the next row exists
			if(x.row + 1  <  r)
			{
				int row = x.row;
				int col  = x.column;
				//adding element of row and same column in the matrix
				queue.add(   new HeapElement( row+1, col, mat[row+1][col] )   );
			}
		}
		return -1;
	}
	
	public static void main(String[] args)
	{
		int i, j, r, c;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the number of rows : ");
		r = s.nextInt();
		System.out.print("Enter the numvber of columns : ");
		c = s.nextInt();
		int matrix[][] = new int[r][c];
		System.out.println("Enter the elements of the matrix : ");
		for(i=0; i<r; i++)
		{
			for(j=0; j<c; j++)
				matrix[i][j] = s.nextInt();
		}
		System.out.println("Enter the integer : ");
		int k = s.nextInt();
		System.out.println("Given matrix : ");
		printMatrix(matrix, r, c);

		int ans = kthSmallestElement(matrix, r, c, k);
		System.out.println("\n\nKth Smallest element is : " + ans);
	}

	static void printMatrix(int mat[][], int r, int c)
	{
		for(int i=0; i<r; i++)
		{
			for(int j=0; j<c; j++)
				System.out.print(mat[i][j] + "  ");
			System.out.println();
		}
	}
}

Time complexity :- O(n*log(n))
Space complexity :- O(n)