3. Median in row wise sorted matrix

3. Median in row wise sorted matrix

Problem link :- click here
Approach ----> Binary search(sort of nested)

//r*c is odd
package progams;

import java.util.Scanner;

public class Matrix__3
{

	/*
	    Median in a row-wise sorted matrix      NOTE :-  r*c   is always odd
	    		       	1    3   5
	    		       	2    6   9
	    		       	3    6   9
	    *) Approach is slightly different. Since the given matrix is of integer (size = 4 bytes)
	     		which can hold up-to   2^32  different elements       ( 4 bytes = 32 bit )
	     		so we can do binary search of 2^32 elements
	    *) but lets shorten the range by finding the minimum and maximum elements
	     		since the matrix is sorted row-wise 
	     			the minimum must be one of the first column elements
	     			and maximum must be one of the last column elements
	     *) now we will do the binary search between those two elements 
	     		taking                                                   min -> low           max -> high
	     		     median should be between one of these element
	     *) we will take                                               average(as mid) = (min + max)/2  
	     		check how many elements are  <=     average
	     			if the number is >=   (r*c+1)/2  then there is median among these elements
	     			median is in left. therefore                     max = average - 1
	     			
	     			if the number is <   (r*c+1)/2  then median must on the right 
	     			therefore                                                   min = average + 1
	     			
	     *) if the famous condition (low<=high) fails then return the value that we have stored(note)
	*/
	
	static int medianOfRowWiseSortedMatrix(int mat[][], int r, int c)
	{
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		
		for(int i=0; i<r; i++)
		{
			//finding the minimum of the first column
			if(mat[i][0]   <  min)
				min = mat[i][0];
			
			//finding the maximum of the last column
			if(mat[i][c-1]   > max)
				max = mat[i][c-1];
		}
		
		//binary search starts here(its like binary search of indices     and returns   value)
		int to_left = (r*c+1)/2;
		while(min <= max)
		{
			int average = (min + max)/2;
			
			int count = numberOfElementsLessThan(mat, r, c, average);
			
			if(to_left  <= count  )
				max = average - 1;
			else
				min = average + 1;
		}
		
		return min;
	}
	
	static int numberOfElementsLessThan(int mat[][], int r, int c, int average)
	{
		/*
		    here we find the number of elements less than average
		    we will do binary search in each row and add the index of the first element > average to the sum
		    index(first element > average)   =   number of elements <= average
		*/
		
		int sum = 0;
		
		for(int i=0; i<r; i++)
		{
			int low = 0;
			int high = c-1;
			
			//binary starts here(its like binary search of values   and  returns   index)
			while(low <= high)
			{
				int mid = (low + high)/2;
				
				 if(mat[i][mid] <= average)
					 low = mid+1;
				 else
					 high = mid-1;
			}
			
			/*
			    here we want the index of first element that is > average 
			    which is pointed by low. because each time the element <= average 
			    						low is update to       mid+1(index of element + 1)
			    whenever the condition fails and all the elements are checked then 'low' is our answer
			*/
			sum = sum + low;
		}
		
		return sum;
	}
	
	
	
	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("Given matrix : ");
		printMatrix(matrix, r, c);

		int ans = medianOfRowWiseSortedMatrix(matrix, r, c);
		System.out.println("\nMedian 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( 32*r* log(c) )
Space complexity :- O(1)