076. Maximal Rectangle in Binary Matrix

Why this mechanism works

At each row, let a column's height count consecutive ones ending at that row. Any all-one rectangle has a bottom row; at that row it appears as a rectangle under these heights. Solving one histogram per bottom row therefore searches all possible rectangles without enumerating every pair of corners.

State and boundaries

heights[c] is the vertical one-run ending at the current row. best is the maximum histogram area over processed bottom rows.

Protocol

1. Initialize column heights to zero.
2. Increment a height for one and reset it for zero.
3. Solve the current histogram.
4. Update the global maximum.

Visualization

row 1: 1 0 1 -> heights 1 0 1
row 2: 1 1 1 -> heights 2 1 2
row 3: 1 1 1 -> heights 3 2 3
last histogram supports area 6

Python implementation

from kata_075 import largest_histogram

def maximal_rectangle(matrix):
    if not matrix or not matrix[0]:
        return 0
    heights = [0] * len(matrix[0])
    best = 0
    for row in matrix:
        for c, value in enumerate(row):
            heights[c] = heights[c] + 1 if value == 1 else 0
        best = max(best, largest_histogram(heights))
    return best

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 maximal_rectangle: if not matrix or not matrix[0]:
matrix=[[1, 0, 1], [1, 1, 1], [1, 1, 1]]

L6 maximal_rectangle: heights = [0] * len(matrix[0])
matrix=[[1, 0, 1], [1, 1, 1], [1, 1, 1]]; heights=[0, 0, 0]

L7 maximal_rectangle: best = 0
matrix=[[1, 0, 1], [1, 1, 1], [1, 1, 1]]; heights=[0, 0, 0]; best=0

L8 maximal_rectangle: for row in matrix:
matrix=[[1, 0, 1], [1, 1, 1], [1, 1, 1]]; heights=[0, 0, 0]; best=0; row=[1, 0, 1]

L9 maximal_rectangle: for c, value in enumerate(row):
matrix=[[1, 0, 1], [1, 1, 1], [1, 1, 1]]; heights=[0, 0, 0]; best=0; row=[1, 0, 1]; c=0; value=1

L10 maximal_rectangle: heights[c] = heights[c] + 1 if value == 1 else 0
matrix=[[1, 0, 1], [1, 1, 1], [1, 1, 1]]; heights=[1, 0, 0]; best=0; row=[1, 0, 1]; c=0; value=1

L9 maximal_rectangle: for c, value in enumerate(row):
matrix=[[1, 0, 1], [1, 1, 1], [1, 1, 1]]; heights=[1, 0, 0]; best=0; row=[1, 0, 1]; c=1; value=0

L9 maximal_rectangle: for c, value in enumerate(row):
matrix=[[1, 0, 1], [1, 1, 1], [1, 1, 1]]; heights=[1, 0, 0]; best=0; row=[1, 0, 1]; c=2; value=1

... 13 intermediate state changes omitted ...

L10 maximal_rectangle: heights[c] = heights[c] + 1 if value == 1 else 0
matrix=[[1, 0, 1], [1, 1, 1], [1, 1, 1]]; heights=[3, 2, 2]; best=3; row=[1, 1, 1]; c=1; value=1

L9 maximal_rectangle: for c, value in enumerate(row):
matrix=[[1, 0, 1], [1, 1, 1], [1, 1, 1]]; heights=[3, 2, 2]; best=3; row=[1, 1, 1]; c=2; value=1

L10 maximal_rectangle: heights[c] = heights[c] + 1 if value == 1 else 0
matrix=[[1, 0, 1], [1, 1, 1], [1, 1, 1]]; heights=[3, 2, 3]; best=3; row=[1, 1, 1]; c=2; value=1

L11 maximal_rectangle: best = max(best, largest_histogram(heights))
matrix=[[1, 0, 1], [1, 1, 1], [1, 1, 1]]; heights=[3, 2, 3]; best=6; row=[1, 1, 1]; c=2; value=1

L4 maximal_rectangle: if not matrix or not matrix[0]:
matrix=[]

Why the solution is correct

The height recurrence exactly measures contiguous upward availability. A histogram rectangle corresponds to an all-one matrix rectangle ending at this row, and every matrix rectangle has such a bottom row. Taking the maximum over rows is therefore complete.

Time and space

O(rows*cols) time and O(cols) working space, including the reused histogram stack.

Common mistakes

Not resetting a height at zero allows rectangles to pass through blocked cells. Summing all column heights gives area without enforcing a shared minimum height.

Reasoning card

Transfer exercise

Find the largest all-zero rectangle by changing only the height-update predicate.