Maximal Rectangle — Solution

Problem

Given a binary matrix of '0's and '1's, find the area of the largest rectangle made entirely of '1's. The rectangle must be axis-aligned — no diagonals.

• Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
• Output: 6
• Explanation: The 2-row by 3-column block of 1s spanning rows 1–2 and columns 2–4 is the largest all-ones rectangle.

Intuition

Imagine looking at the matrix one row at a time and asking: at each cell, how many consecutive 1s are stacked directly above (including this row)? That gives you a histogram of bar heights. Finding the largest rectangle in that histogram — a classic monotonic stack problem — tells you the best all-ones rectangle whose bottom edge runs through this row. Repeat for every row and track the global maximum.

Solution — Histogram Reduction with Monotonic Stack

For each row, build an array of heights where heights[j] counts consecutive 1s ending at that row in column j. Then apply the "largest rectangle in histogram" algorithm using a stack that maintains bar indices in increasing height order. When a shorter bar is encountered, each taller bar is popped and its rectangle area is computed with the current index as the right boundary.

1. Initialize a heights array of zeros, one entry per column.
2. For each row, update heights[j] — increment if the cell is '1', reset to 0 if '0'.
3. Append a sentinel height of 0 to force all remaining bars out of the stack at the end of each histogram pass.
4. Maintain a monotonic increasing stack of column indices. For each index i:
   • While the top bar is taller than current_height, pop it and compute area: height × width, where width is i − stack[-1] − 1 if the stack is still non-empty, otherwise just i.
5. Push the current index onto the stack.
6. Track the global maximum area across all rows and all pops.

1def maximalRectangle(matrix: list[list[str]]) -> int:
2    if not matrix:
3        return 0
4    num_cols = len(matrix[0])
5    heights = [0] * num_cols
6    max_area = 0
7
8    for row in matrix:
9        for col in range(num_cols):
10            # Grow column height on '1'; reset entirely on '0' to break the streak
11            heights[col] = heights[col] + 1 if row[col] == '1' else 0
12
13        max_area = max(max_area, _largest_rect_in_histogram(heights))
14
15    return max_area
16
17
18def _largest_rect_in_histogram(heights: list[int]) -> int:
19    stack = []  # column indices, kept so heights[stack[-1]] is non-decreasing
20    max_area = 0
21
22    for i in range(len(heights) + 1):
23        # Sentinel 0 at position len(heights) forces all remaining bars to be processed
24        current_height = heights[i] if i < len(heights) else 0
25        while stack and heights[stack[-1]] > current_height:
26            popped_height = heights[stack.pop()]
27            # Width reaches back to whatever is now exposed on the stack top
28            width = i if not stack else i - stack[-1] - 1
29            max_area = max(max_area, popped_height * width)
30        stack.append(i)
31
32    return max_area

Time: O(n·m) — each row does an O(m) height update and an O(m) histogram pass (every index is pushed and popped at most once).
Space: O(m) — the heights array and stack are each proportional to the number of columns.

Complexity Summary

Common Mistakes

• Not resetting heights to 0 for a '0' cell — heights must be reset entirely, not decremented; a single '0' breaks the consecutive streak and the height must restart from zero on the next '1'.
• Forgetting the sentinel 0 at the end of the histogram pass — bars still in the stack after the loop represent rectangles that extend to the right edge, and without the sentinel those areas are silently skipped.
• Width miscalculation when the stack is empty after a pop — the rectangle spans from column 0 to the current position, so width = i, not i - 0 - 1 = i - 1.
• Comparing cells as integers — matrix cells are the characters '0' and '1'; checking row[col] == 1 always fails in Python and Java without an explicit cast.
• Running the histogram on a single row's raw values — the heights array accumulates across rows (increment for each '1', reset for each '0'); resetting heights per row would only find single-row rectangles.

Related Problems

• largest-rectangle-in-histogram — the exact subroutine used as the inner loop; solving this first makes the matrix problem straightforward
• maximal-square — same binary matrix setup but restricted to squares; solved with pure DP instead of a stack
• trapping-rain-water — another monotonic stack problem on bar heights, similar pop-and-compute pattern
• sum-of-subarray-minimums — uses the same "pop when you see something smaller" monotonic stack structure
• 01-matrix — distance queries in a binary matrix; different algorithm but the same row-by-row binary matrix traversal mindset