Introduction

In matrix problems, "finding rectangles enclosing 0" usually means finding a rectangular region made entirely of zero values. A brute-force search over all submatrices is too slow for anything beyond toy input, so the practical solution is to transform the matrix into a form that can be scanned row by row.

Reducing the Problem to Histograms

Assume you have a grid of numbers and want the largest rectangle that contains only zeros. First convert the matrix into a running height table:

• If the current cell is zero, increase the height from the row above by one.
• If the current cell is non-zero, reset the height to zero.

After processing one row, the heights describe a histogram. Any all-zero rectangle ending at that row becomes a rectangle in the histogram. That means you can solve the matrix problem by solving the "largest rectangle in a histogram" problem for each row.

Efficient Algorithm

The histogram subproblem can be solved in linear time with a monotonic stack. For each bar:

1. Keep indices of increasing heights on the stack.
2. When the current height is smaller than the height at the stack top, pop.
3. The popped bar defines the height of a maximal rectangle.

Doing that for every row gives total complexity O(rows * cols).

1def largest_zero_rectangle(matrix):
2    if not matrix or not matrix[0]:
3        return 0
4
5    cols = len(matrix[0])
6    heights = [0] * cols
7    best = 0
8
9    for row in matrix:
10        for c, value in enumerate(row):
11            heights[c] = heights[c] + 1 if value == 0 else 0
12        best = max(best, largest_histogram_area(heights))
13
14    return best
15
16
17def largest_histogram_area(heights):
18    stack = []
19    best = 0
20
21    for i in range(len(heights) + 1):
22        current = heights[i] if i < len(heights) else 0
23
24        while stack and current < heights[stack[-1]]:
25            h = heights[stack.pop()]
26            left = stack[-1] if stack else -1
27            width = i - left - 1
28            best = max(best, h * width)
29
30        stack.append(i)
31
32    return best
33
34
35grid = [
36    [1, 0, 0, 1, 0],
37    [0, 0, 0, 1, 0],
38    [0, 0, 1, 1, 0],
39    [0, 0, 0, 0, 0],
40]
41
42print(largest_zero_rectangle(grid))

For this input, the function returns the area of the largest all-zero rectangle.

Recovering Coordinates

Sometimes the area is not enough. You may also need the top-left and bottom-right corners. You can extend the histogram routine to track:

• 'height, from the popped bar'
• 'width, from the current index and previous smaller index'
• bottom row, which is the current matrix row
• top row, which is bottom - height + 1

The left and right boundaries come from the stack state when the bar is popped. That gives exact rectangle coordinates without changing the asymptotic complexity.

What If You Need Every Rectangle

Finding the single largest rectangle is efficient. Enumerating every all-zero rectangle is a different problem and can be much more expensive because the number of valid rectangles itself may be large. For example, an all-zero n x m matrix contains many zero-only subrectangles, so output size alone can dominate runtime.

If the real goal is "find all maximal zero rectangles", define "maximal" carefully first. In many applications, maximal rectangles are enough and keep the result set manageable.

Common Pitfalls

The main mistake is using a four-loop or six-loop brute-force solution with repeated submatrix scans. That quickly becomes unusable.

Another mistake is mixing up "rectangles that include at least one zero" with "rectangles composed entirely of zeros". Those require different checks.

A third issue is ignoring edge cases such as an empty matrix, a matrix with no zeros, or a matrix that is entirely zero. The histogram approach handles these cases cleanly if the reset and sentinel logic are implemented correctly.

Summary

• Convert each row into histogram heights of consecutive zeros.
• Solve the largest-rectangle-in-histogram problem for every row.
• The full algorithm runs in O(rows * cols) time.
• Track boundaries during stack pops if you need rectangle coordinates.
• Enumerating every valid zero rectangle is a harder problem than finding the largest one.