Question

How to find the largest‑rectangle‑of‑zeros in a 0/1 matrix with C++

Answer 1

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

using std::vector;

// ------------------------------------------------------------
// Computes the largest rectangle area in a histogram.
// The histogram heights represent consecutive zeros
// in each column up to the current row.
// ------------------------------------------------------------
int largestHistogram(vector<int>& h) {
    std::stack<int> st;     // stores indices of bars in increasing height order
    int maxArea = 0;
    int n = h.size();

    // Process each bar in the histogram
    for (int i = 0; i < n; i++) {

        // While the current bar is lower than the bar at stack top,
        // we finalize rectangles that end at index i-1.
        while (!st.empty() && h[st.top()] >= h[i]) {
            int height = h[st.top()];
            st.pop();

            // Width is either from 0..i-1 or between two smaller bars
            int width = st.empty() ? i : i - st.top() - 1;

            maxArea = std::max(maxArea, height * width);
        }

        // Push current index
        st.push(i);
    }

    // Final cleanup: process remaining bars in stack
    while (!st.empty()) {
        int height = h[st.top()];
        st.pop();

        // Width extends to the end of histogram
        int width = st.empty() ? n : n - st.top() - 1;

        maxArea = std::max(maxArea, height * width);
    }

    return maxArea;
}

// ------------------------------------------------------------
// Computes the largest rectangle consisting entirely of 0s
// in a binary matrix.
// Converts each row into a histogram of consecutive zeros
// and applies largestHistogram().
// ------------------------------------------------------------
int largestZeroRectangle(vector<vector<int>>& mat) {
    int R = mat.size();
    int C = mat[0].size();

    vector<int> height(C, 0);  // histogram heights for each column
    int best = 0;

    // Build histogram row by row
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {

            // If cell is 0, increase height; otherwise reset to 0
            if (mat[i][j] == 0)
                height[j]++;
            else
                height[j] = 0;
        }

        // Compute largest rectangle for this histogram
        best = std::max(best, largestHistogram(height));
    }

    return best;
}

int main() {
    vector<vector<int>> mat = {
        {0,0,1,0,0,1},
        {0,0,0,0,0,0},
        {1,0,0,0,0,1},
        {1,1,0,0,0,1},
        {1,1,1,1,1,1}
    };

    std::cout << largestZeroRectangle(mat) << std::endl;
}



/*
run:

9

*/

 

70+ SQL courses for beginners and professionals