← Back to DSA Animator
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).