Largest submatrix of all 1’s in a binary matrix

Problem Statement : Given a binary matrix(matrix that have only 1’s and 0’s), find the largest rectangular submatrix that have only 1’s.

Explanation:
We need to construct a matrix of histograms from given matrix. The height of histogram at a cell(H[i][j]) would be number of consecutive 1’s above the current cell along with current cell itself.

Ex: For the binary matrix

0 0 0 0 1
1 1 0 0 1
0 0 1 1 1
0 0 1 1 1
1 1 1 1 1

Histogram matrix would be

0 0 0 0 1
1 1 0 0 2
0 0 1 1 3
0 0 2 2 4
1 1 3 3 5

Now, we need to traverse the matrix and calculate the maximum area possible for each histogram. For this to understand, please refer this page. Observe the graphs shown in the link to understand how to calculate the maximum possible rectangular area in histograms. In our histogram matrix, each row can be considered as a separate histogram and should keep track of maximum area possible for the complete matrix.

Code :

#include <bits/stdc++.h>

using namespace std;

int maxArea(int a[][100],int m,int n)
{
	int area = 0,count,temp;
	/*
	 *Finds maximum area of rectangle from the histograms build.
	*/
	for(int i = 0;i < m;i++)
	{
		for(int j = 0;j < n;j++)
		{
			if(a[i][j] > 0)
			{
				count = a[i][j];
				temp = j-1;
				while(temp >= 0 && a[i][temp] >= a[i][j])
				{
					count+=a[i][j];
					temp--;
				}
				temp = j+1;
				while(temp < n && a[i][temp] >= a[i][j])
				{
					count += a[i][j];
					temp++;
				}
				if(count > area)
					area = count;
			}
		}
	}
    return area;
}

int solve(int a[][100],int m,int n)
{
	int temp = 0;
	/*
	 *Sets a[i][j] to consecutive 1's above it till that cell.
     *It is like building histograms on each row with size of histogram at 
     *an index of a row as number of consecutive 1's till that index.
    */
    for(int i = 0;i < n;i++)
	{
		for(int j = 0;j < m;j++)
		{
			if(a[i][j] == 1)
			{
				if(i >= 1)
					a[i][j] = a[i-1][j] + 1;
				else
					a[i][j] = 1;
			}
		}
	}
    return maxArea(a,m,n);
}

int main()
{
	int m,n;
	scanf("%d %d",&m,&n);
	int a[100][100];
	for(int i = 0;i < m;i++)
	{
		for(int j = 0;j < n;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	printf("%d\n",solve(a,m,n));
	return 0;
}
Ex :
Matrix A[][]

5 5
0 1 0 1 1
0 1 0 0 1
1 1 1 1 1
0 1 1 1 0
0 0 1 0 1

Histogram matrix H[][] will be

0 1 0 1 1
0 2 0 0 2
1 3 1 1 3
0 4 2 2 0
0 0 3 0 1

When calculated for maximum area in histogram, the cells H[3][2] and H[3][3] give count = 6 and is the maximum area over any other cell in matrix H. In the code, I wrote values of histogram matrix in given matrix(A) itself so that no extra space is used to solve the problem.

For any doubts on this topic, comment below.

Advertisements