LeetCode 85 - Maximal Rectangle

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Stack, Matrix, Monotonic Stack

Solution

Problem Understanding

The problem asks us to find the area of the largest rectangle containing only 1s in a binary matrix. The matrix consists of characters '0' and '1', where '1' represents a valid cell that may belong to a rectangle and '0' represents a blocked cell that cannot be included.

The key requirement is that the rectangle must contain only consecutive 1s, and it must form a proper rectangle aligned with the matrix grid. We are not looking for the largest connected component or irregular shape. Instead, we want the rectangle with the maximum area, where:

$$\text{area} = \text{height} \times \text{width}$$

The input is a rows x cols matrix of strings, where each entry is either '0' or '1'. The output is a single integer representing the area of the largest valid rectangle.

For example, consider:

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

The largest rectangle here is:

1 1 1
1 1 1

with width 3 and height 2, producing an area of 6.

The constraints tell us:

1 <= rows, cols <= 200
Each value is either '0' or '1'

Since the matrix can contain up to:

$$200 \times 200 = 40,000$$

cells, a highly inefficient brute-force solution could become prohibitively slow. We need an algorithm that scales reasonably for this input size.

Several edge cases stand out immediately. A matrix containing only 0s should return 0. A matrix with only one cell should return either 0 or 1 depending on the value. Single-row and single-column matrices are important because rectangle formation becomes constrained. Another tricky case is when rectangles appear to extend but are interrupted by a single 0, which can invalidate larger candidate rectangles.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to try every possible rectangle in the matrix and verify whether it consists entirely of 1s.

We could enumerate all possible top-left and bottom-right corners. For every candidate rectangle, we scan all cells inside it to ensure they are all '1'. If valid, we compute its area and update the maximum.

Suppose the matrix dimensions are m x n.

There are:

O(m²) choices for row boundaries
O(n²) choices for column boundaries

For each rectangle, validating all cells may take O(mn) time.

This leads to:

$$O(m^3 \times n^3)$$

time complexity in the worst case.

Although this approach is conceptually simple and guaranteed to find the correct answer because it checks every possible rectangle, it is far too slow for matrices up to 200 x 200.

Key Insight for an Optimal Solution

The important observation is that this problem can be transformed into a sequence of Largest Rectangle in Histogram problems.

For each row, imagine building a histogram where each column stores the number of consecutive 1s ending at that row.

For example:

Matrix:
1 0 1 1
1 1 1 1
1 1 1 0

After processing row by row:

Row 0 heights: [1,0,1,1]
Row 1 heights: [2,1,2,2]
Row 2 heights: [3,2,3,0]

Each row now represents a histogram.

The question becomes:

What is the largest rectangle in this histogram?

We already know an optimal O(n) monotonic stack solution for Largest Rectangle in Histogram.

Since we solve one histogram per row:

m rows
O(n) histogram computation per row
O(n) stack processing per row

Total complexity becomes:

$$O(m \times n)$$

which is efficient enough.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m³ × n³)	O(1)	Checks every possible rectangle
Optimal	O(m × n)	O(n)	Converts each row into histogram and uses monotonic stack

Algorithm Walkthrough

Optimal Strategy: Histogram + Monotonic Stack

Handle edge cases

If the matrix is empty, return 0 immediately. Although the constraints guarantee at least one row and column, defensive coding is still good practice. 2. Initialize histogram heights

Create an array called heights of length cols, initialized to 0.

Each position represents the height of consecutive 1s ending at the current row. 3. Process each row

Iterate through every row in the matrix.

For every column:

If the cell is '1', increment heights[col]
If the cell is '0', reset heights[col] = 0

This transforms the current row into a histogram. 4. Solve Largest Rectangle in Histogram

For the updated histogram, compute the largest rectangle using a monotonic increasing stack.

The stack stores indices of histogram bars.

The invariant is:

Heights in the stack remain increasing.

Maintain monotonicity

As we scan each bar:

While the current height is smaller than the stack top height, pop from the stack.
Calculate area using the popped bar as the limiting height.

Width calculation:

If stack becomes empty:

width = current_index

Otherwise:

width = current_index - stack[-1] - 1

Flush remaining stack

Append an extra 0 height at the end conceptually.

This forces all remaining bars to be processed. 7. Track maximum area

Keep updating the global maximum rectangle area across all rows. 8. Return result

After processing every row, return the maximum area found.

Why it works

At every row, heights[i] correctly represents the height of consecutive 1s ending at that row. Any rectangle ending at the current row must correspond to some contiguous section of this histogram. The monotonic stack guarantees that every bar is processed exactly once as the smallest height of a maximal rectangle. Since every possible histogram rectangle is considered, and every row is examined, the algorithm finds the largest rectangle in the matrix.

Python Solution

from typing import List

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
        max_area = 0

        def largest_rectangle_area(histogram: List[int]) -> int:
            stack = []
            max_histogram_area = 0

            extended_histogram = histogram + [0]

            for index, height in enumerate(extended_histogram):
                while stack and extended_histogram[stack[-1]] > height:
                    top_index = stack.pop()
                    rectangle_height = extended_histogram[top_index]

                    if not stack:
                        width = index
                    else:
                        width = index - stack[-1] - 1

                    area = rectangle_height * width
                    max_histogram_area = max(
                        max_histogram_area,
                        area
                    )

                stack.append(index)

            return max_histogram_area

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

            max_area = max(
                max_area,
                largest_rectangle_area(heights)
            )

        return max_area

The implementation follows the algorithm directly.

We first initialize the heights array, which stores consecutive counts of 1s for each column. As we process rows, each '1' extends the histogram upward, while each '0' resets the corresponding height to zero.

The helper function largest_rectangle_area() solves the histogram problem in linear time. A monotonic increasing stack stores indices of bars. When a shorter bar appears, taller bars are popped and evaluated because their maximal extent is now known.

Appending a sentinel 0 ensures all remaining bars are processed without requiring special cleanup logic.

For every row, we compute the histogram maximum and update the global answer.

Go Solution

func maximalRectangle(matrix [][]byte) int {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return 0
	}

	cols := len(matrix[0])
	heights := make([]int, cols)
	maxArea := 0

	largestRectangleArea := func(histogram []int) int {
		stack := []int{}
		maxHistogramArea := 0

		extended := make([]int, len(histogram)+1)
		copy(extended, histogram)

		for i := 0; i < len(extended); i++ {
			for len(stack) > 0 &&
				extended[stack[len(stack)-1]] > extended[i] {

				topIndex := stack[len(stack)-1]
				stack = stack[:len(stack)-1]

				height := extended[topIndex]

				var width int
				if len(stack) == 0 {
					width = i
				} else {
					width = i - stack[len(stack)-1] - 1
				}

				area := height * width
				if area > maxHistogramArea {
					maxHistogramArea = area
				}
			}

			stack = append(stack, i)
		}

		return maxHistogramArea
	}

	for _, row := range matrix {
		for col := 0; col < cols; col++ {
			if row[col] == '1' {
				heights[col]++
			} else {
				heights[col] = 0
			}
		}

		area := largestRectangleArea(heights)
		if area > maxArea {
			maxArea = area
		}
	}

	return maxArea
}

The Go implementation closely mirrors the Python version, but there are some language-specific details.

The matrix uses [][]byte, so comparisons must be against '1' and '0' characters rather than strings. Slice operations are used to emulate stack behavior, where removing the top element is done with:

stack = stack[:len(stack)-1]

Go does not support appending a literal sentinel during iteration as conveniently as Python, so an extended slice is created with one extra zero element.

Since the constraints are small, integer overflow is not a concern.

Worked Examples

Example 1

Input:

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

Row 0

Histogram:

[1,0,1,0,0]

Index	Height	Largest Area
0	1	1
1	0	1
2	1	1
3	0	1
4	0	1

Maximum so far = 1

Row 1

Update heights:

[2,0,2,1,1]

Largest histogram rectangle:

2 × 1 = 2
1 × 3 = 3

Maximum so far = 3

Row 2

Update heights:

[3,1,3,2,2]

Largest rectangle:

height = 2
width = 3
area = 6

Maximum so far = 6

Row 3

Update heights:

[4,0,0,3,0]

Largest rectangle = 4

Final answer:

Example 2

Input:

[["0"]]

Histogram:

[0]

No rectangle exists.

Answer:

Example 3

Input:

[["1"]]

Histogram:

[1]

Largest rectangle:

1 × 1 = 1

Answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n)	Each row is processed once, each histogram bar pushed and popped at most once
Space	O(n)	Heights array and monotonic stack

The algorithm processes every cell exactly once while building histograms. For each row, the histogram solution runs in linear time because every index enters and leaves the stack at most once. Since there are m rows and n columns, total complexity is:

$$O(m \times n)$$

The extra memory consists of the histogram array and stack, both proportional to the number of columns.

Test Cases

solution = Solution()

assert solution.maximalRectangle(
    [["1", "0", "1", "0", "0"],
     ["1", "0", "1", "1", "1"],
     ["1", "1", "1", "1", "1"],
     ["1", "0", "0", "1", "0"]]
) == 6  # Provided example

assert solution.maximalRectangle(
    [["0"]]
) == 0  # Single zero

assert solution.maximalRectangle(
    [["1"]]
) == 1  # Single one

assert solution.maximalRectangle(
    [["1", "1", "1", "1"]]
) == 4  # Single row, all ones

assert solution.maximalRectangle(
    [["1"],
     ["1"],
     ["1"]]
) == 3  # Single column

assert solution.maximalRectangle(
    [["0", "0"],
     ["0", "0"]]
) == 0  # All zeros

assert solution.maximalRectangle(
    [["1", "1"],
     ["1", "1"]]
) == 4  # Entire matrix rectangle

assert solution.maximalRectangle(
    [["1", "0", "1"],
     ["1", "1", "1"],
     ["1", "1", "0"]]
) == 4  # Interrupted rectangle

assert solution.maximalRectangle(
    [["1", "1", "0", "1"],
     ["1", "1", "0", "1"],
     ["1", "1", "1", "1"]]
) == 6  # Tall rectangle plus wider candidate

assert solution.maximalRectangle(
    [["1"] * 200 for _ in range(200)]
) == 40000  # Maximum constraint size

Test	Why
Provided example	Validates core logic
`[['0']]`	Smallest invalid rectangle
`[['1']]`	Smallest valid rectangle
Single row all ones	Tests horizontal expansion
Single column all ones	Tests vertical expansion
All zeros	Ensures zero reset logic works
Full matrix of ones	Largest rectangle equals matrix size
Interrupted rectangle	Ensures `0` correctly breaks rectangles
Mixed rectangle shapes	Verifies maximum selection
`200 x 200` all ones	Stress test at constraint limit

Edge Cases

Matrix Contains Only Zeros

A matrix consisting entirely of '0' values is an important edge case because no rectangle exists. A buggy implementation might accidentally compute a nonzero area if stack handling or initialization is incorrect.

For example:

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

Our implementation handles this naturally because every histogram height stays 0, so no positive rectangle area is ever formed.

Single Row or Single Column

When the matrix has only one row or one column, rectangle formation becomes restricted. Some implementations incorrectly assume two-dimensional expansion is always possible.

For example:

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

should return 3.

Similarly:

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

should also return 3.

Since the algorithm reduces every row to a histogram, these cases work automatically.

Rectangles Interrupted by a Single Zero

A particularly tricky scenario occurs when a promising rectangle is interrupted by a single 0.

Example:

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

A naive approach may mistakenly count disconnected regions together.

Our histogram reset logic prevents this. Whenever a 0 appears:

heights[col] = 0

This guarantees rectangles cannot incorrectly span broken columns.

Remaining Stack Elements After Traversal

A subtle implementation bug in histogram problems happens when increasing heights remain in the stack at the end.

Example:

[1,2,3,4]

Without special handling, rectangles involving the last bars might never be computed.

The sentinel 0 appended to the histogram ensures every remaining bar is popped and evaluated correctly.