Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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

Author Pranav Gautam
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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.

Click here to know about: AngularJS

Happy Coding!

Previous article
Finding the Minimum Cost to Reduce the Array by Merging the Adjacent Elements Repetitively
Next article
Count of sequence of length K in the range [1, N] where every element is a multiple of its previous one
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass