7. Find a specific pair in Matrix

7. Find a specific pair in Matrix

Problem link :- click here

package progams;

import java.util.Scanner;

public class Matrix__7
{

	/*
	    Given a N x N matrix mat[N][N] of integers, find the maximum value of 
	    			mat(c, d)    -    mat(a, b)          such that  c > a        d > b
	    
	    				   1         2        -1        -4       -20
	    			       -8        -3         4         2         1
	    			        3         8         6         1         3
	    			       -4        -1         1         7        -6
	    			        0        -4        10        -5         1
	    			        
	    In this example the output is 18             10 - (-8)
	              there is     10 - (-20) = 30  
	              but this is not the correct answer because        c(10)  =  2          c(-20) =  4
	              			this doesn't holds the condition          d > b   (false)
	              	
	    lets create another matrix to store the maximum element       
	    among the columns to right of that column                 and 
	    among the rows              below that  row
	    
	    lets start from the last column                            and       last row       
	    because there is no more column to right          and       no more row below that row
	    
	    after initializing the matrix 
	    find the maximum difference  among     max[i][j]  -  mat[i][j]          these values.
	*/
	
	static int maxDifference(int mat[][], int n)
	{
		int max[][] = new int[n][n];
		
		max[n-1][n-1]   =   mat[n-1][n-1];
		
		//initializing last row
		int max1 = mat[n-1][n-1];
		for(int i=n-2; i>=0; i--)
		{
			if(max1 < mat[n-1][i])
				max1 = mat[n-1][i];
			max[n-1][i] = max1;
		}
		
		//initializing last column
		max1 = mat[n-1][n-1];
		for(int i=n-2; i>=0; i--)
		{
			if(max1 < mat[i][n-1])
				max1 = mat[i][n-1];
			max[i][n-1] = max1;
		}
		
		//initializing all other elements 
		for(int i=n-2; i>=0; i--)
		{
			for(int j=n-2; j>=0; j--)
			{
				//maximum element to right and down 
				//and right and down element also has maximum
				max1 = Math.max(  max[i][j+1],   max[i+1][j]  );
				max[i][j] = Math.max( mat[i][j], max1 );
			}
		}
		
		//finding the maximum element
		int max_diff = Integer.MIN_VALUE;
		for(int i=0; i<n; i++)
		{
			for(int j=0; j<n; j++)
			{
				int diff = max[i][j] - mat[i][j];
				max_diff = Math.max(max_diff, diff);
			}
		}
		
		return max_diff;
	}
	
	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 = maxDifference(matrix, r);
		System.out.println("\n\nMaximum difference 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²)
Space complexity :- O(n²)