Maximal Rectangle — Histogram per Row

Problem

Find the largest rectangle containing only 1s in a binary matrix.

Approach — Histogram per Row

For each row, build cumulative heights (height=0 if cell is '0'). Apply Largest Rectangle in Histogram to each row's heights.

Time: O(m*n) | Space: O(n)

Solutions

Python

class Solution:
    def maximalRectangle(self, matrix: list[list[str]]) -> int:
        if not matrix: return 0
        n=len(matrix[0]); heights=[0]*n; best=0
        def largest_rect(h):
            stk=[-1]; mx=0; h=h+[0]
            for i,x in enumerate(h):
                while stk[-1]!=-1 and h[stk[-1]]>=x:
                    ht=h[stk.pop()]; w=i-stk[-1]-1; mx=max(mx,ht*w)
                stk.append(i)
            return mx
        for row in matrix:
            heights=[heights[j]+1 if row[j]=='1' else 0 for j in range(n)]
            best=max(best,largest_rect(heights))
        return best

Complexity

Time: O(m*n) | Space: O(n)