Problem Statement
Maximal Rectangle
You are given a grid filled with the characters '1' and '0'. Your job is to find the biggest solid rectangle made entirely of '1's, and report its area (the number of cells inside it). The clever trick: read the grid one row at a time, and picture each row as the floor of a bar chart. For every column, the bar's height is how many '1's stack up without a break, going up from the current row. A bar chart like this is called a histogram, just a row of bars of different heights sitting side by side. Once you turn a row into a histogram, finding the largest all-'1's rectangle that ends on that row is the same as finding the largest rectangle you can draw inside that histogram. So you solve a smaller, well known problem (largest rectangle in a histogram) once per row, and keep the best answer.
Signals to notice
Brute force first
Check every rectangle — O(n²m²).
The key insight
Per-row histogram heights + monotonic stack for largest rectangle. Max across rows. O(mn).
Trace it on matrix=[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
init: heights=[0,0,0,0,0], max_area=0 row0 "1 0 1 0 0": heights=[1,0,1,0,0] -> histogram max=1, max_area=1 row1 "1 0 1 1 1": heights=[2,0,2,1,1] -> best is cols2-4 height1*width3=3, max_area=3 row2 "1 1 1 1 1": heights=[3,1,3,2,2] -> best is cols2-4 height2*width3=6, max_area=6 row3 "1 0 0 1 0": heights=[4,0,0,3,0] -> best is col0 height4*width1=4, max_area stays 6 no rows left -> return max_area = 6
What must stay true
Each row creates a histogram of consecutive 1s above. Largest rectangle in each histogram is a candidate.
Shape of the loop
heights = [0] * cols
for each row in matrix:
for j: heights[j] = (row[j]=='1') ? heights[j]+1 : 0 # reset on 0
max_area = max(max_area, largestRectInHistogram(heights)) # monotonic stack
return max_areaPseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not resetting height on 0 — height[j] = 0 when cell is 0.