Maximal Rectangle: Histogram Stack on Every Row

LeetCode 85, Maximal Rectangle, is one of those problems that looks terrifying at first glance. You get a binary matrix of "0"s and "1"s and need to find the largest rectangle containing only ones. Brute force over every possible rectangle is O(rows^2 * cols^2), which is way too slow. But there is a beautiful reduction that turns this 2D problem into a series of 1D problems you may already know how to solve: largest rectangle in histogram.

The trick is to build a histogram of heights for each row, then run a monotonic stack on each histogram. If you have already solved LeetCode 84 (Largest Rectangle in Histogram), the maximal rectangle problem is just that, applied once per row.

The problem

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

matrix = [
    ["1","0","1","0","0"],
    ["1","0","1","1","1"],
    ["1","1","1","1","1"],
    ["1","0","0","1","0"],
]
# Output: 6

The maximal rectangle spans rows 1-2, columns 2-4. That is 2 rows by 3 columns, area 6.

The brute force

The naive approach checks every possible rectangle in the matrix: pick a top-left corner, pick a bottom-right corner, verify that every cell inside is a "1". With an m x n matrix, there are O(m^2 * n^2) possible rectangles, and verifying each takes O(m * n) work, giving O(m^3 * n^3) total. That is unusable for the constraint of 200 x 200.

You can optimize the verification with prefix sums, but it still does not get you to the optimal solution. The real insight is to change your perspective entirely.

The key insight: histograms row by row

Imagine standing at each row and looking upward. For each column, count how many consecutive "1"s there are going up from the current row. That gives you a histogram of heights. Then the question becomes: what is the largest rectangle in this histogram?

For our example matrix:

• Row 0: Heights = [1, 0, 1, 0, 0] (just the first row)
• Row 1: Heights = [2, 0, 2, 1, 1] (column 0 has two 1s stacked, column 1 resets to 0)
• Row 2: Heights = [3, 1, 3, 2, 2] (everything grows by 1 where there is a "1")
• Row 3: Heights = [4, 0, 0, 3, 0] (columns with "0" reset to 0)

The update rule is simple. If matrix[r][c] == "1", then heights[c] += 1. Otherwise, heights[c] = 0. That is it.

Now for each row, you have a histogram. Finding the largest rectangle in a histogram is a classic monotonic stack problem. You solve it once per row and track the global maximum.

At row 2, the histogram [3, 1, 3, 2, 2] gives us the largest rectangle of area 6: columns 2 through 4 at height 2. That is the answer for the whole matrix.

Largest rectangle in histogram (the helper)

Before writing the full solution, let's nail the histogram helper. This is LeetCode 84, and it is the building block that makes everything work.

The idea: walk through the bars left to right. Maintain a stack of indices in increasing order of height. When you encounter a bar shorter than the stack top, pop and compute the area of the rectangle that the popped bar could have formed.

def largest_rectangle_in_histogram(heights):
    stack = []  # indices of bars in increasing height order
    max_area = 0
    n = len(heights)

    for i in range(n + 1):
        # Use height 0 as a sentinel to flush the stack at the end
        h = heights[i] if i < n else 0

        while stack and h < heights[stack[-1]]:
            popped_height = heights[stack.pop()]
            # Width extends from just after the new stack top to i-1
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, popped_height * width)

        stack.append(i)

    return max_area

A few things to notice:

1. The sentinel trick. We iterate to n (one past the end) with height 0. This forces every remaining bar off the stack, so we do not need a separate cleanup loop after the main loop.
2. Width calculation. When we pop a bar, the width of its rectangle is not just "from here to i." It extends left all the way back to whatever is now on top of the stack (the previous shorter bar). If the stack is empty, the popped bar was the shortest so far, and the width spans from index 0 to i-1, which is just i.
3. Each index is pushed once and popped once. The total work across all iterations of the while loop is O(n).

The full solution

Now we combine the row-by-row histogram update with the histogram helper:

def maximal_rectangle(matrix):
    if not matrix or not matrix[0]:
        return 0

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

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

        # Find largest rectangle in this row's histogram
        max_area = max(max_area, largest_rectangle_in_histogram(heights))

    return max_area

That is the entire solution. The outer loop processes each row, updating the heights array in O(cols) time. The inner call to largest_rectangle_in_histogram is also O(cols). So the total time is O(rows * cols), which is just the size of the matrix. You cannot do better than that because you have to read every cell at least once.

Complexity analysis

Time: O(rows * cols). For each of the rows rows, we do O(cols) work to update the histogram and O(cols) work for the monotonic stack pass. Total: O(rows * cols).

Space: O(cols). We keep one heights array of length cols and one stack that holds at most cols elements at any time.

The histogram stack approach is both the fastest and the most space-efficient.

Common mistakes

1. Forgetting to reset heights to 0. When matrix[r][c] == "0", the height must go back to zero, not just stop growing. A "0" breaks the vertical run of ones completely.

2. Off-by-one in the width calculation. When the stack is empty after a pop, the width is i, not i - 1. This catches the case where the popped bar was the shortest in the entire histogram so far. Drawing a small example on paper clears this up fast.

3. Forgetting the sentinel. If you stop iterating at n - 1 instead of n, bars remaining on the stack never get processed. You will miss rectangles that extend to the right edge of the histogram. The sentinel (an extra iteration with height 0) is the cleanest fix.

4. Treating the matrix values as integers. LeetCode gives the matrix as strings ("0" and "1"), not integers. Comparing row[c] == 1 instead of row[c] == "1" will silently produce wrong answers in Python.

Why this is a monotonic stack problem

The histogram step is the same monotonic stack pop loop you see in Daily Temperatures and Trapping Rain Water. The comparison and the "what you compute on pop" change, but the structure is identical:

while stack and compare(current, stack[-1]):
    popped = stack.pop()
    # compute something using popped and current
stack.append(current)

For Daily Temperatures, you compare with > and compute a distance. For the histogram, you compare with < (current bar is shorter than the popped bar) and compute an area. Same brick, different wall.

The monotonic stack here maintains bars in increasing height order. When a shorter bar arrives, it means the taller bars to its left can no longer extend rightward. Pop them, compute their areas, and move on. That is the entire idea.

The building blocks

This problem is built on two reusable pieces:

1. Row-by-row histogram update

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

This transforms a 2D matrix problem into a sequence of 1D histogram problems. You will see this same trick in other matrix problems where you want to consider "rectangles ending at each row."

2. Monotonic stack for largest rectangle in histogram

The pop loop with the width calculation:

while stack and h < heights[stack[-1]]:
    popped_height = heights[stack.pop()]
    width = i if not stack else i - stack[-1] - 1
    max_area = max(max_area, popped_height * width)
stack.append(i)

This is the same building block from the monotonic-stack family. If you can write this from memory, you can solve Largest Rectangle in Histogram, Maximal Rectangle, and several other hard problems without hesitation.

Edge cases

Before submitting, check these:

• Single cell [["1"]]: answer is 1. Single cell [["0"]]:** answer is 0.
• All ones: the answer is rows * cols.
• All zeros: the answer is 0. Heights never grow above 0.
• Single row [["1","0","1","1"]]: this degenerates to largest rectangle in histogram on one row. Answer is 2.
• Single column: the histogram has one bar that keeps growing. Answer is the longest vertical run of ones.

The histogram + monotonic stack approach handles all of these without any special-case code.

From understanding to recall

You now see how Maximal Rectangle reduces to the histogram stack problem. The reduction is clean: update heights per row, run the stack, track the max. But can you reproduce this under interview pressure?

There are two pieces to drill: the histogram update (trivial once you remember it) and the largest-rectangle-in-histogram helper (the tricky part). The helper has a few moving parts: the sentinel, the width calculation when the stack is empty vs. not, and the comparison direction (< not >). These are exactly the kind of details that slip away after a week.

Spaced repetition fixes that. Instead of solving this once and hoping it sticks, you write the histogram stack from scratch at increasing intervals. After a few reps, the sentinel trick and the width formula are locked in, and you can apply them to any histogram-stack variant.

Related posts

• Daily Temperatures - The classic introduction to monotonic stacks, using the same pop loop with a different comparison
• Trapping Rain Water - Another problem where you reason about "how far does this bar extend," solved optimally with two pointers but also solvable with a monotonic stack
• Stack Patterns - The full overview of stack patterns, from bracket matching to monotonic stacks

CodeBricks breaks the histogram stack pattern into its reusable pieces and drills them individually. You type the pop loop and the width calculation from scratch each time, building the muscle memory so that when you see Maximal Rectangle or Largest Rectangle in Histogram in an interview, the code flows without hesitation.