visual walkthrough
Maximal Rectangle
Reduces a 2D grid to repeated histogram problems.
The idea
Every all-1 rectangle has a bottom row. Standing on that row, the columns above look like a bar chart: each bar is how many 1s are stacked up to here.
So solve "largest rectangle in a histogram" (a monotonic stack) once per row, updating the bars as you go down.
Complexity
| approach | time | space |
|---|---|---|
| Grow from every corner | O(R² · C²) | O(1) |
| Row by row histograms | O(R · C) | O(C) |