Maximal Rectangle [Hard] — Histogram Stack per Row

Problem Statement

Given a binary matrix of 0s and 1s, find the largest rectangle containing only 1s and return its area.

Input:
[["1","0","1","0","0"],
 ["1","0","1","1","1"],
 ["1","1","1","1","1"],
 ["1","0","0","1","0"]]
Output: 6

Intuition

For each row, compute the height of consecutive 1s above (including current). Then apply "Largest Rectangle in Histogram" on this heights array.

Solutions

C++

int largestHistogram(vector<int>& h) {
    h.push_back(0);
    stack<int> stk; int mx=0;
    for (int i=0;i<h.size();i++) {
        while (!stk.empty()&&h[i]<h[stk.top()]) {
            int ht=h[stk.top()]; stk.pop();
            int w=stk.empty()?i:i-stk.top()-1;
            mx=max(mx,ht*w);
        }
        stk.push(i);
    }
    return mx;
}
int maximalRectangle(vector<vector<char>>& matrix) {
    if(matrix.empty()) return 0;
    int m=matrix.size(), n=matrix[0].size(), mx=0;
    vector<int> heights(n,0);
    for (auto& row:matrix) {
        for (int j=0;j<n;j++) heights[j]=row[j]=='1'?heights[j]+1:0;
        mx=max(mx,largestHistogram(heights));
        heights.back()=0; // clean sentinel
    }
    return mx;
}

Python

def maximalRectangle(matrix: list[list[str]]) -> int:
    if not matrix: return 0
    n = len(matrix[0])
    heights = [0] * n
    max_area = 0

    def largest_hist(h):
        h = h + [0]
        stack, mx = [], 0
        for i, v in enumerate(h):
            while stack and v < h[stack[-1]]:
                ht = h[stack.pop()]
                w = i if not stack else i - stack[-1] - 1
                mx = max(mx, ht * w)
            stack.append(i)
        return mx

    for row in matrix:
        for j in range(n):
            heights[j] = heights[j] + 1 if row[j] == '1' else 0
        max_area = max(max_area, largest_hist(heights))
    return max_area

Complexity

Time: O(m×n)
Space: O(n)