Maximal Rectangle

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

Hints

· Stuck? Reveal one nudge at a time.

Process the matrix row by row and turn each row into a histogram.

heights[j] = consecutive 1s in column j ending at the current row (reset on a 0).

The biggest all-1s rectangle bottoming out on a row is the largest rectangle in that histogram.

Common doubts

Every maximal 1-rectangle has a bottom row; over that row, its columns are exactly the histogram bars, so its area is a rectangle in that histogram.

A 0 breaks the vertical run of 1s in that column, so the histogram bar there restarts from zero.

No — update it incrementally in O(cols) per row, so the whole thing is O(rows x cols).

Interview follow-ups

· What an interviewer asks next.

That has a simpler O(rows x cols) DP: dp[i][j] = 1 + min of the three neighbors when the cell is 1.

Track, when you update the best area in the histogram routine, the row, the popped height, and the left/right boundaries.

Fun facts

Reducing a 2D problem to a stack of 1D histograms is a hallmark technique — it turns an intimidating matrix problem into one you already know.
This is the standard follow-up to Largest Rectangle in Histogram in interviews.

Asked at

AmazonGoogleMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: matrix = [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]
Output: 6
The largest all-1s rectangle is the 2x3 block in the middle, area 6.

Example 2

Input: matrix = [[0]]
Output: 0
No 1s, so the area is 0.

Constraints

- 1 <= rows, cols <= 200 - matrix[i][j] is 0 or 1

Process the matrix row by row, turning each row into a histogram: heights[j] is the number of consecutive 1s in column j ending at the current row (reset to 0 on a 0). The largest all-1s rectangle ending on that row is exactly the largest rectangle in that histogram — the problem you already solved. Take the max over all rows.

Prerequisites

Before you start

· Concepts used directly in the solution.

Largest rectangle in histogram. The monotonic-stack routine that finds the biggest rectangle under a histogram.

Column run-lengths. heights[j] counts consecutive 1s up to the current row, forming that row's histogram.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The rectangle

“Must the rectangle be axis-aligned and contiguous?”

Yes — a solid block of 1s.

“What if the matrix is empty or all 0s?”

The answer is 0.

The ideal opening — say it like this

I reduce this to Largest Rectangle in Histogram, row by row.

For each row I keep, per column, the number of consecutive 1s ending there — that's a histogram.

The largest all-1s rectangle bottoming out on that row is the largest rectangle in that histogram; I take the max across rows.

Understand the problem

Worked example — a matrix whose row histograms peak at a 2x3 block

matrix rows -> histograms -> per-row max rectangle
the overall answer is the largest of those per-row maxima

Key observations

1Aha

Each row is a histogram of column run-lengths

heights[j] = consecutive 1s in column j ending at the current row. A 0 resets it; a 1 extends it.

2Aha

Reduce to histogram rectangles

The biggest all-1s rectangle with its bottom on a given row is precisely the largest rectangle in that row's histogram.

3Aha

Every rectangle is seen once

Any maximal 1-rectangle has a bottom row; it's counted when that row's histogram is processed, so the row-wise maximum is the global answer.

Brute force vs optimal

	Brute histogram per row	Stack histogram per row
Idea	Row histograms, expand each bar (O(cols^2))	Row histograms, monotonic stack (O(cols))
Time	O(rows * cols^2)	O(rows * cols)
Space	O(cols)	O(cols)

Both build the same histograms; they differ only in how each row's largest rectangle is computed. Full code is in the Approaches selector below.

Summary

Key takeaway

Build a running histogram of consecutive 1s per column, row by row; the largest all-1s rectangle ending on each row is the largest rectangle in that histogram. Take the max over rows — O(rows x cols) with the stack histogram.

heights = [0]*cols
for each row:
    for j: heights[j] = heights[j] + 1 if row[j] == 1 else 0
    best = max(best, largestRectangleInHistogram(heights))
return best