LeetCode 85: Maximal Rectangle

Problem Restatement

We are given a binary matrix filled with characters:

"0"
"1"

We need to find the largest rectangle that contains only "1" cells and return its area.

The rectangle must be axis-aligned. That means its sides follow the matrix rows and columns.

The official problem states: given a rows x cols binary matrix filled with 0s and 1s, find the largest rectangle containing only 1s and return its area. Example 1 uses matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] and returns 6.

Input and Output

Function shape:

class Solution:
    def maximalRectangle(self, matrix: list[list[str]]) -> int:
        ...

Examples

Example 1:

matrix = [
    ["1", "0", "1", "0", "0"],
    ["1", "0", "1", "1", "1"],
    ["1", "1", "1", "1", "1"],
    ["1", "0", "0", "1", "0"],
]

The largest rectangle has area:

6

One such rectangle uses rows 1 to 2 and columns 2 to 4:

1 1 1
1 1 1

Answer:

6

Example 2:

matrix = [["0"]]

There is no rectangle of 1s.

Answer:

0

Example 3:

matrix = [["1"]]

The single cell itself is the largest rectangle.

Answer:

1

First Thought: Try Every Rectangle

A rectangle can be described by four boundaries:

top
bottom
left
right

We could try every possible rectangle and check whether all cells inside it are "1".

That is correct, but too slow.

For a matrix with R rows and C columns, there are many choices:

O(R^2 * C^2)

rectangles.

Checking each rectangle cell by cell makes it even slower.

We need to reuse work.

Key Insight

Each row can be treated as the bottom of a histogram.

For every column, count how many consecutive "1" cells appear above the current row, including the current row.

For example, after processing this row:

["1", "1", "1", "1", "1"]

inside the matrix:

[
    ["1", "0", "1", "0", "0"],
    ["1", "0", "1", "1", "1"],
    ["1", "1", "1", "1", "1"],
]

the heights are:

[3, 1, 3, 2, 2]

because:

Now the problem becomes:

Find the largest rectangle in this histogram.

That is exactly LeetCode 84.

So we solve LeetCode 85 by running the histogram solution once per row.

Building Heights

Maintain an array:

heights = [0] * cols

For each row:

If matrix[row][col] == "1":

heights[col] += 1

If matrix[row][col] == "0":

heights[col] = 0

The reset is necessary because a rectangle of 1s cannot pass through a 0.

Histogram Helper

Given a histogram:

heights = [3, 1, 3, 2, 2]

we use a monotonic increasing stack.

The stack stores indices whose heights are increasing.

When the current height is smaller than the height at the stack top, we pop the stack and compute the best rectangle where the popped bar is the limiting height.

Use a sentinel 0 at the end to flush all remaining bars.

for i, h in enumerate(heights + [0]):

For each popped bar:

height = heights[stack.pop()]
left = stack[-1] if stack else -1
width = i - left - 1
area = height * width

Algorithm

Let:

rows = len(matrix)
cols = len(matrix[0])

Initialize:

heights = [0] * cols
best = 0

For each row:

1. Update heights.
2. Treat heights as a histogram.
3. Compute the largest rectangle in that histogram.
4. Update best.

Return best.

Walkthrough

Use:

matrix = [
    ["1", "0", "1", "0", "0"],
    ["1", "0", "1", "1", "1"],
    ["1", "1", "1", "1", "1"],
    ["1", "0", "0", "1", "0"],
]

After row 0:

heights = [1, 0, 1, 0, 0]

Largest histogram rectangle:

1

After row 1:

heights = [2, 0, 2, 1, 1]

Largest histogram rectangle:

3

The rectangle is the three 1s at the end of row 1.

After row 2:

heights = [3, 1, 3, 2, 2]

Largest histogram rectangle:

6

This corresponds to:

1 1 1
1 1 1

After row 3:

heights = [4, 0, 0, 3, 0]

Largest histogram rectangle:

4

The global maximum is:

6

Correctness

Every all-1 rectangle has a bottom row.

When the algorithm processes that bottom row, each column in the rectangle has a height at least equal to the rectangle height, because all cells above the bottom row inside that rectangle are 1.

So that rectangle appears as a valid rectangle inside the histogram for its bottom row.

The histogram helper computes the largest rectangle for that row. Therefore, when processing the bottom row of any valid matrix rectangle, the algorithm considers an area at least as large as that rectangle.

The algorithm processes every row as a possible bottom row. Therefore, it considers the optimal rectangle.

Also, every rectangle found in a row histogram corresponds to real 1 cells in the matrix, because each histogram height counts consecutive 1s ending at the current row. So the algorithm never counts a rectangle containing 0.

Thus the maximum area returned is exactly the largest rectangle containing only 1s.

Complexity

Let:

R = number of rows
C = number of columns

For each row, we update C heights and run a C-column histogram scan.

Implementation

class Solution:
    def maximalRectangle(self, matrix: list[list[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0

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

        def largest_histogram_area(values: list[int]) -> int:
            stack = []
            ans = 0

            for i, h in enumerate(values + [0]):
                while stack and h < values[stack[-1]]:
                    height = values[stack.pop()]
                    left = stack[-1] if stack else -1
                    width = i - left - 1
                    ans = max(ans, height * width)

                stack.append(i)

            return ans

        for row in matrix:
            for col in range(cols):
                if row[col] == "1":
                    heights[col] += 1
                else:
                    heights[col] = 0

            best = max(best, largest_histogram_area(heights))

        return best

Code Explanation

We first handle an empty matrix:

if not matrix or not matrix[0]:
    return 0

Then create one height per column:

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

For each row, update the histogram:

if row[col] == "1":
    heights[col] += 1
else:
    heights[col] = 0

A 1 extends the vertical run.

A 0 breaks the vertical run.

The helper largest_histogram_area is the LeetCode 84 stack algorithm.

This loop adds a sentinel zero:

for i, h in enumerate(values + [0]):

When the current height is smaller than the stack top, we compute completed rectangles:

while stack and h < values[stack[-1]]:

The popped height is the limiting rectangle height:

height = values[stack.pop()]

The next smaller bar on the left is:

left = stack[-1] if stack else -1

The current index is the next smaller bar on the right.

So the width is:

width = i - left - 1

Then update the best histogram area:

ans = max(ans, height * width)

After each row, update the global answer:

best = max(best, largest_histogram_area(heights))

Testing

def run_tests():
    s = Solution()

    assert s.maximalRectangle([
        ["1", "0", "1", "0", "0"],
        ["1", "0", "1", "1", "1"],
        ["1", "1", "1", "1", "1"],
        ["1", "0", "0", "1", "0"],
    ]) == 6

    assert s.maximalRectangle([["0"]]) == 0
    assert s.maximalRectangle([["1"]]) == 1
    assert s.maximalRectangle([["0", "0"]]) == 0
    assert s.maximalRectangle([["1", "1"]]) == 2

    assert s.maximalRectangle([
        ["1"],
        ["1"],
        ["1"],
    ]) == 3

    assert s.maximalRectangle([
        ["1", "1", "1"],
        ["1", "1", "1"],
    ]) == 6

    assert s.maximalRectangle([
        ["1", "0", "1"],
        ["1", "1", "1"],
        ["1", "1", "0"],
    ]) == 4

    print("all tests passed")

run_tests()

Test meaning: