Finding the area of the largest rectangle in a binary matrix

Given : A binary matrix ( two dimensional array ) filled with all 1s or 0s.
Objective : Finding the area of the largest sub-matrix in the given binary matrix that is filled with all 1s.

Example : In the below given rectangles, we could see that the area of
Largest rectangle in Matrix 1 = 6 units.
Largest rectangle in Matrix 2 = 5 units.
Largest rectangle in Matrix 3 = 3 units.

binary_matrix

The idea to find the area of the largest ‘1’ filled rectangle, is based on finding the area of the largest rectangle in the histogram.

We create a histogram from each row of the given binary matrix by adding numbers from the next row.

  • The first row of the histogram will contain all the elements of the first row of the binary matrix.
  • Each column / bar of the histogram will grow in size by adding the numbers greater than 0 from the next row.
  • The column / bar of the histogram will reset to height 0 if the number in the current row is 0.

We calculate the area of all the histograms thus created and return the area of the largest histogram, which would be the same as the area of the largest ‘1’ filled rectangle in the binary matrix.

See the below example :

Binary_Matrix_Histogram



Program for finding the area of the largest rectangle filled with all ‘1’s in a binary matrix

#include<iostream>
#include<stack>
#include<vector>

using namespace std;
typedef vector<int> VI;
typedef stack<int> SI;

int GetArea (vector<int> histogram) {

    int sz = histogram.size();
    stack<int> stack_of_height, stack_of_position;
    int area = 0;
    int index = 0, height = 0;

    for (int pos=0; pos<sz; pos++) {
        // If the height of the current bar is greater than the height 
        // at the top of stack push it.
        if ( stack_of_height.empty() || stack_of_height.top() <= histogram[pos] ) {
            stack_of_height.push(histogram[pos]);
            stack_of_position.push(pos);
        } else {
            if ( stack_of_height.top() > histogram[pos] ) {
                // If the height of the current bar is less than the height at the top of 
                // the stack, pop out all the bigger heights and their corresponding positions 
                // and find the maximum area.
                while ( !stack_of_height.empty() && stack_of_height.top() > histogram[pos] ) {
                    index  = stack_of_position.top();
                    stack_of_position.pop();
                    height = stack_of_height.top();
                    stack_of_height.pop();
                    area = max(area, height * (pos-index));
                }
                // Note: We are pushing height of the current bar and the position of the last removed
                // index.
                stack_of_height.push(histogram[pos]);
                stack_of_position.push(index);
            }
        }
    }

    while (!stack_of_height.empty()) {
        int tempArea = stack_of_height.top() * (histogram.size() - stack_of_position.top());
        stack_of_height.pop();
        stack_of_position.pop();
        if (tempArea > area) {
            area = tempArea;
        }
    }
    return area;
}

int main() {

    vector<vector<int>> mat_0 = { { 0, 0, 0, 0, 0, 0, 1 },
                                  { 0, 0, 0, 0, 1, 1, 1 },
                                  { 1, 1, 1, 1, 1, 1, 1 },
                                  { 0, 0, 0, 1, 1, 1, 1 } }; //9

    vector<vector<int>> mat_1 = { { 1, 0, 1, 0, 0 },
                                  { 1, 0, 1, 1, 1 },
                                  { 1, 1, 1, 1, 1 },
                                  { 1, 0, 0, 1, 0 } }; //6

    vector<vector<int>> mat_2 = { { 1, 0, 1, 1, 0, 1, 1, 1 } }; // 3

    vector<vector<vector<int>>> binary_matrix_list = { mat_0, mat_1, mat_2 };

    for (auto matrix : binary_matrix_list) {

        vector<int> histogram;
        int area = 0;
        cout << "\nMatrix " << endl;
        for (auto row : matrix) {

            // Print the given binary matrix
            for (auto num : row)
                cout << num << " ";
            cout << endl;

            // Find the area of the histogram formed by adding elements of the previous row.

            if (histogram.size() == 0) { // Add all the numbers of the first row.
                for (auto num : row)
                    histogram.push_back(num);
            } else {
                for (int i=0; i<row.size(); i++) {
                    // If the number in the column position of the current row is 0, reset the histogram column to 0.
                    // Else add the number to the histogram column.
                    if (row[i] == 0) {
                        histogram[i] = 0;
                    } else {
                        histogram[i] += row[i];
                    }
                }
            }
            area = max(area, GetArea(histogram));
        }
        cout << "Area : " << area << endl;
    }
    return 0;
}

Output


Matrix 
0 0 0 0 0 0 1 
0 0 0 0 1 1 1 
1 1 1 1 1 1 1 
0 0 0 1 1 1 1 
Area : 9

Matrix 
1 0 1 0 0 
1 0 1 1 1 
1 1 1 1 1 
1 0 0 1 0 
Area : 6

Matrix 
1 0 1 1 0 1 1 1 
Area : 3


Copyright (c) 2019-2021, Algotree.org.
All rights reserved.