6. Maximum size rectangle in a binary matrix

6. Maximum size rectangle in a binary matrix

Problem link :- click here

package progams;

import java.util.Scanner;
import java.util.Stack;

public class Matrix__6
{

	/*
	    Given a binary matrix. Find the maximum area of a rectangle formed only of 1's in the given matrix.
	    
	    we are going to use   Array__36   largest rectangle formed from histogram         
	    			as a sub problem for this problem
	    we know how to find the largest rectangle of the given array
	    lets divide the problem and make a number of problems of arrays
	    
	    1) lets send the first row as a array to the function
	    		array[i] = mat[0][i]
	    2) we will create a array for each from 2nd row using the following protocols
	    			1) if the value of mat[1][i]  ==  1
	    						array[i] = mat[1][i] + array[i]
	    			2) if the value of mat[1][i]  ==  0
	*/
	
	//Array__36   largest rectangle of histogram
	static int maxAreaOfAnArray(int height[], int n)
	{
		Stack<Integer> my_stack = new Stack<>();
		
		int left[] = new int[n];
		int right[] = new int[n];
		
		//initializing left array
		left[0] = 0;
		my_stack.push(0);
		for(int i=1; i<n; i++)
		{
			while(  !my_stack.empty()    &&   height[ my_stack.peek() ]  >=  height[i]  )
				my_stack.pop();
			if(my_stack.empty())
				left[i] = 0;
			else if( height[my_stack.peek()]  < height[i] )
				left[i] = my_stack.peek() + 1;
			
			my_stack.push(i);
		}
		
		//clear the stack before using it for initialization of right array
		while( !my_stack.empty() )
			my_stack.pop();
		
		//initializing right array
		right[n-1] = n-1;
		my_stack.push(n-1);
		for(int i=n-1; i>=0; i--)
		{
			while( !my_stack.empty()  &&  height[ my_stack.peek() ] >= height[i] )
				my_stack.pop();
			if( my_stack.empty() )
				right[i] = n-1;
			else if( height[ my_stack.peek() ]  < height[i]  )
				right[i] = my_stack.peek() - 1;
			
			my_stack.push(i);
		}
		
		
		//problem starts here
		int max_area = 0;
		for(int i=0; i<n; i++)
		{
			int area = height[i] * ( right[i] - left[i] + 1 );
			
			max_area = Math.max(max_area, area);
		}
		
		return max_area;
	}
	
	static int maxAreaOfMatrix(int mat[][], int r, int c)
	{
		int arr[] = new int[c];
		for(int i=0; i<c; i++)
			arr[i] = mat[0][i];
		
		int max_area = maxAreaOfAnArray(arr, c);
		
		for(int i=1; i<r; i++)
		{
			//updating array 
			for(int j=0; j<c; j++)
			{
				if( mat[i][j] == 1 )
					arr[j] = arr[j] + mat[i][j];
				else
					arr[j] = 0;
			}
			
			//calling maximum area of an array
			int area = maxAreaOfAnArray(arr, c);
			max_area = Math.max(max_area, area);
		}
		
		return max_area;
	}
	
	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 = maxAreaOfMatrix(matrix, r, c);
		System.out.println("\n\nMaximum area of the rectangle 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(r*c)
Space complexity :- O(c)