Maximal Rectangle in Binary Matrix

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

Key Insight

Treat each row as the ground level of a histogram. For each cell, the “height” is the number of consecutive 1s above it (including itself). Then apply the largest rectangle in histogram algorithm to each row.

Building Heights

Matrix:          Heights row by row:
1 0 1 0 0        [1, 0, 1, 0, 0]
1 0 1 1 1   →    [2, 0, 2, 1, 1]
1 1 1 1 1        [3, 1, 3, 2, 2]
1 0 0 1 0        [4, 0, 0, 3, 0]

For row 2: column 0 has three consecutive 1s above → height 3.

Solution

def maximal_rectangle(matrix):
    """
    Find maximal rectangle of 1s in binary matrix.
    Time: O(m × n), Space: O(n)
    """
    if not matrix or not matrix[0]:
        return 0

    cols = len(matrix[0])
    heights = [0] * cols
    max_area = 0

    for row in matrix:
        # Update heights
        for j in range(cols):
            heights[j] = heights[j] + 1 if row[j] == '1' else 0

        # Apply largest rectangle in histogram
        max_area = max(max_area, _largest_rect(heights))

    return max_area


def _largest_rect(heights):
    stack = []
    max_area = 0
    heights_with_sentinel = heights + [0]

    for i, h in enumerate(heights_with_sentinel):
        while stack and heights_with_sentinel[stack[-1]] > h:
            height = heights_with_sentinel[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

Trace

Row 0: heights = [1,0,1,0,0] → largest rect = 1
Row 1: heights = [2,0,2,1,1] → largest rect = 3 (1×3 from cols 2-4)
Row 2: heights = [3,1,3,2,2] → largest rect = 6 (2×3 from cols 2-4)
Row 3: heights = [4,0,0,3,0] → largest rect = 4 (4×1 from col 0)

Max area: 6

Complexity

DP Alternative

There’s a DP approach using left/right boundaries, but the histogram approach is more intuitive and equally efficient.

Edge Cases

• All 0s — returns 0
• All 1s — returns m × n
• Single row/column — degenerates to 1D problem
• Integer vs string matrix — check if values are '1' or 1

When to Use This Pattern

Reducing a 2D problem to repeated 1D problems is a powerful technique. It appears in:

• Maximum sum rectangle in a 2D matrix
• Largest plus sign in a grid
• Count submatrices with all ones

Related Problems

• Largest Rectangle in Histogram (LeetCode 84) — the 1D subroutine
• Count Submatrices With All Ones (LeetCode 1504)
• Maximum Sum Rectangle — Kadane’s algorithm extended to 2D