DSA AnimatorDSA animations
Maximal Rectangle LC #85 Hard Stack · Histogram per Row
Problem

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

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
Explanation: The maximal rectangle spans columns 2–4 of rows 1–2, giving area = 6.
Example 2
Input: matrix = [["0"]]
Output: 0
Example 3
Input: matrix = [["1"]]
Output: 1
Constraints: 1 ≤ rows, cols ≤ 200  |  matrix[i][j] is '0' or '1'
Try Examples
Custom:
Matrix & Heights
Heights Array
Monotonic Stack (index : height)
empty
Variables
Row r
—
Col c
—
heights[c]
—
maxArea
0
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Init heights[0..n-1] = 0, maxArea = 0
2
For each row r: update heights[c] += 1 if cell is '1', else reset to 0
3
Run largest-rectangle-in-histogram on heights[] using monotonic stack
4
When popping index i: area = heights[i] × width; update maxArea
5
Return maxArea after all rows
Time
O(m×n)
Space
O(n)
Why It Works

For each row, heights[c] counts how many consecutive '1's end at that cell going upward. This transforms each row into a histogram problem (LC 84). The largest rectangle in that histogram is the biggest all-'1' rectangle whose bottom edge sits on that row. Running this for every row and taking the maximum gives the global answer in O(m × n).

How to solve Maximal Rectangle

LeetCode 85 · Hard · Stack · Pattern: Histogram per Row

Why the obvious approach is slow

Checking every possible rectangle is far too slow. But each row can be turned into the previous problem: Largest Rectangle in Histogram.

The key idea

Build a histogram for each row: the height of a column is the number of consecutive 1s ending at that row. A 0 resets that column to height 0. Run the histogram stack algorithm on each row, and keep the largest area.

Remember

A 2D rectangle problem becomes a 1D histogram per row. Reuse the monotonic stack from problem 84.

Run the animation above on your own input, or watch the 1:25 video explanation of Maximal Rectangle with a dry run and Java code.

More Stack problems