1.
Problem Statement
1.1.
Input
1.2.
Output
1.3.
Explanation
2.
Approach
3.
Program to Find Largest Rectangle in a Histogram
3.1.
Input
3.2.
Output
4.
Algorithm
5.
Program
5.1.
Input
5.2.
Output
6.
Complexity Analysis
7.
Key Takeaways
Last Updated: Mar 27, 2024

# Maximum size of rectangle in a binary matrix

Pranav Gautam
0 upvote
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

## Problem Statement

Given a matrix with only binary values, find the area of the largest rectangle possible with all 1s.

### Input

``````Enter Number of Rows in the matrix: 4
Enter Number of Columns in the matrix: 5
Enter the matrix values:
1   0   1   0   0
1   0   1   1   1
1   1   1   1   1
1   0   0   1   0``````

### Output

``Area of the largest matrix with all 1s: 6``

### Explanation

In the figure given below, the largest rectangle with all 1s is indicated as orange.

Also Read, Byte Array to String

## Approach

Letâ€™s assume the number of rows in the given matrix to be â€˜Râ€™. Similarly, assume the number of columns to be â€˜Câ€™. Consider the matrix given as input in the Problem Statement. The matrix can be divided into 1 to â€˜Râ€™ rows. Refer to the image given below for illustration.

Letâ€™s take the first row of the matrix. Assume every cell with value 1 as the bar with height 1. Similarly, Assume every cell with the value 0 as the bar with height 0. So, the first row can be converted to the histogram like the figure given below. As you can see here, the area of the largest rectangle with all 1s is 1.

We must know how to find the area of the largest rectangle in a histogram to solve the given problem. You can practice finding the area of the largest rectangle in a histogram on our practice platform at Largest rectangle in a histogram.  If you canâ€™t figure out the solution, refer to the The Largest Rectangular Area in Histogram blog to learn how to find the area of the largest rectangle in a histogram.

Now, add the 2nd row to the histogram. Letâ€™s call the first-row â€˜PREVIOUS_ROWâ€™. Similarly, 2nd row will be called â€˜CURRENT_ROWâ€™. The row created by using â€˜PREVIOUS_ROWâ€™ and â€˜CURRENT_ROWâ€™ will be called â€˜RESULTANT_ROWâ€™. The values of cells of the â€˜RESULTANT_ROWâ€™ are given according to the instructions given below.

• If the current column in â€˜CURRENT_ROWâ€™ is not 0, add the values of the cells of â€˜PREVIOUS_ROWâ€™ and â€˜CURRENT_ROWâ€™. Store the result into the â€˜RESULTANT_ROWâ€™.

• If the current cell in the â€˜CURRENT_ROWâ€™ is 0, assign the value of  0 to the â€˜RESULTANT_ROWâ€™.

Refer to the figure given below for a clear understanding of the instructions.

The resultant histogram created using the values of â€˜RESULTANT_ROWâ€™ will look like the figure given below.

Similarly, all the rows can be added to create the resultant histograms for all the cumulative rows. At any row, if the histogram has the area of the largest rectangle encountered so far, the value of the area will be stored as the new answer. To find the area of the largest rectangle of the histogram, use the â€˜LARGEST_RECTANGLEâ€™ function explained in our The Largest Rectangular Area in Histogram blog. For a quick revision, the code to find the â€˜LARGEST_RECTANGLEâ€™ is given below.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Program to Find Largest Rectangle in a Histogram

``````#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int largestRectangle(vector<int> &heights)
{
int n = heights.size();

/*	The stack holds indexes of heights[] array.
The bars stored in the stack are always in
increasing order of their heights.
*/
stack<int> currentStack;

// Initialize max area.
int maxArea = 0;

// To store the top of the stack.
int topOfStack = 0;

// To store an area with the top bar as the smallest bar.
int areaWithTop = 0;

// Run through all bars of a given histogram.
int i = 0;
while (i < n)
{

/*  If this bar is higher than the bar on the top stack,
push it to stack.
*/

if (currentStack.empty() || heights[currentStack.top()] <= heights[i])
{
currentStack.push(i++);
}
else
{

/*	Calculate the area with heights[topOfStack]
stack as the smallest bar.
*/
topOfStack = heights[currentStack.top()];
currentStack.pop();
areaWithTop = topOfStack * i;

if (!currentStack.empty())
areaWithTop = topOfStack * (i - currentStack.top() - 1);

maxArea = max(maxArea, areaWithTop);
}
}

/*	Now pop the remaining bars from the stack and
calculate the area with every popped bar
as the smallest bar.
*/
while (!currentStack.empty())
{
topOfStack = heights[currentStack.top()];
currentStack.pop();
areaWithTop = topOfStack * i;

if (!currentStack.empty())
areaWithTop = topOfStack * (i - currentStack.top() - 1);

maxArea = max(maxArea, areaWithTop);
}
return maxArea;
}

int main()
{
int numHeights;
cout << "Enter number of heights: ";
cin >> numHeights;

vector<int> heights(numHeights);
cout << "Enter heights of the histogram\n";
for (int i = 0; i < numHeights; i++)
cin >> heights[i];
cout << "Area of largest rectangle in histogram: ";
cout << largestRectangle(heights);
}``````

### Input

``````Enter number of heights: 3
Enter heights of the histogram
1 2 3``````

### Output

``Area of largest rectangle in histogram: 3``

The algorithm to use the â€˜LARGEST_RECTANGLEâ€™ function in finding the area of the largest rectangle with all 1s is given below.

## Algorithm

• Set â€˜MAX_AREAâ€™ equal to the 0.
• Initialize â€˜PREVIOUS_ROWâ€™ and â€˜RESULTANT_ROWâ€™ vectors with values 0 and â€˜TOTAL_COLUMNSâ€™ size.
• For â€˜CURRENT_ROWâ€™ from 0 to â€˜TOTAL_ROWSâ€™, do:
• For â€˜CURRENT_COLUMNâ€™ from 0 to â€˜TOTAL_COLUMNSâ€™, do:
• If MATRIX[CURRENT_ROW][CURRENT_COLUMN] is not 0, then:
• Set RESULTANT_ROW[CURRENT_COLUMN] = PREVIOUS_ROW[CURRENT_COLUMN] + MATRIX[CURRENT_ROW][CURRENT_COLUMN]
• Else:
• Set RESULTANT_ROW[CURRENT_COLUMN] = 0.
• Set â€˜CURRENT_MAX_AREAâ€™ = LARGEST_RECTANGLE(â€˜RESULTANT_ROWâ€™ ).
• Set â€˜MAX_AREAâ€™ = max(â€˜MAX_AREAâ€™ , â€˜CURRENT_MAX_AREAâ€™ ).
• Set â€˜PREVIOUS_ROWâ€™ = â€˜RESULTANT_ROWâ€™.
• Return â€˜MAX_AREAâ€™.

## Program

``````#include <iostream>
#include <vector>
#include <climits>
#include <stack>
using namespace std;

int largestRectangle(vector<int> &heights)
{
int n = heights.size();

/* The stack holds indexes of heights[] array.
The bars stored in the stack are always in
increasing order of their heights.
*/
stack<int> currentStack;

// Initialize max area.
int maxArea = 0;

// To store the top of the stack.
int topOfStack = 0;

// To store an area with the top bar as the smallest bar.
int areaWithTop = 0;

// Run through all bars of a given histogram.
int i = 0;
while (i < n)
{

/*  If this bar is higher than the bar on the top stack,
push it to stack.
*/

if (currentStack.empty() || heights[currentStack.top()] <= heights[i])
{
currentStack.push(i++);
}
else
{

/* Calculate the area with heights[topOfStack]
stack as the smallest bar.
*/
topOfStack = heights[currentStack.top()];
currentStack.pop();
areaWithTop = topOfStack * i;

if (!currentStack.empty())
areaWithTop = topOfStack * (i - currentStack.top() - 1);

maxArea = max(maxArea, areaWithTop);
}
}

/*	Now pop the remaining bars from the stack and
calculate the area with every popped bar
as the smallest bar.
*/
while (!currentStack.empty())
{
topOfStack = heights[currentStack.top()];
currentStack.pop();
areaWithTop = topOfStack * i;

if (!currentStack.empty())
areaWithTop = topOfStack * (i - currentStack.top() - 1);

maxArea = max(maxArea, areaWithTop);
}
return maxArea;
}

int maxMatrixArea(vector<vector<int>> &matrix)
{
int totalRows = matrix.size();
int totalColumns = matrix[0].size();
int maxArea = 0;

// Initialize 'PREVIOUS_ROW' and 'RESULTANT_ROW' vectors with values 0 and 'TOTAL_COLUMNS' size.
vector<int> previousRow(totalColumns, 0), resultantRow(totalColumns, 0);

for (int currentRow = 0; currentRow < totalRows; currentRow++)
{
for (int currentColumn = 0; currentColumn < totalColumns; currentColumn++)
{
/*	If the current column in 'CURRENT_ROW' is not 0,
add the values of the cells of 'PREVIOUS_ROW' and 'CURRENT_ROW'.
*/
if (matrix[currentRow][currentColumn] != 0)
{
resultantRow[currentColumn] = previousRow[currentColumn] + matrix[currentRow][currentColumn];
}
else
{
/*	If the current cell in the 'CURRENT_ROW' is 0,
Assign the value of  0 to the 'RESULTANT_ROW'.
*/
resultantRow[currentColumn] = 0;
}
}

// Find maximum area possible for current resulting histogram.
int currentMaxArea = largestRectangle(resultantRow);

// Comparing the current largest area in the histogram with the largest area so far.
maxArea = max(maxArea, currentMaxArea);

previousRow = resultantRow;
}
return maxArea;
}

int main()
{

// Creating the binary matrix.
int totalRows, TotalColumns;
cout << "Enter Number of Rows in the matrix: ";
cin >> totalRows;
cout << "Enter Number of Columns in the matrix: ";
cin >> TotalColumns;
cout << "Enter the matrix values:\n";
vector<vector<int>> matrix(totalRows, vector<int>(TotalColumns));
for (int i = 0; i < totalRows; i++)
{
for (int j = 0; j < TotalColumns; j++)
{
cin >> matrix[i][j];
}
}
cout << "Area of the largest matrix with all 1s: ";

// Calling the helper function to find the maximum area in the binary matrix.
cout << maxMatrixArea(matrix);
}``````

### Input

``````Enter Number of Rows in the matrix: 4
Enter Number of Columns in the matrix: 5
Enter the matrix values:
1   0   1   0   0
1   0   1   1   1
1   1   1   1   1
1   0   0   1   0``````

### Output

``Area of the largest matrix with all 1s: 6``

## Complexity Analysis

Time Complexity: The size of the input vector for the largestReactangle() function is equal to the â€˜TOTAL_COLUMNSâ€™. The area of the largest rectangle in a histogram runs in linear time. So, the time complexity for largestReactangle()  is O( TOTAL_COLUMNS). For every row from 1 to â€˜TOTAL_ROWSâ€™, the area of the largest rectangle in a histogram is calculated. So, the time complexity for the program is O(TOTAL_ROWS x TOTAL_COLUMNS), where â€˜TOTAL_ROWSâ€™ and â€˜TOTAL_COLUMNSâ€™ represent the total number of rows and columns in the binary matrix respectively.

Space Complexity: Additional space is required to store each row in a stack for the largestReactangle()  function. Every row has a â€˜TOTAL_COLUMNSâ€™ number of elements. So, the space complexity is O(â€˜TOTAL_COLUMNSâ€™), where  â€˜TOTAL_COLUMNSâ€™ represent the total number of columns in the binary matrix.

Check out this problem - Check If A String Is Palindrome

## Key Takeaways

Donâ€™t just stop your learning here. There is so much more to learn. Coding Ninjas is here for you to help in your quest for more learning. If you donâ€™t know where to start from, choose one of our guided paths. Listen to your inner voice and head over to  Coding Ninjas Studio. You can practice top problems, attempt mock tests, read engaging interview experiences, and much more.