Maximal Rectangle
hardTime: O(m*n)Space: O(n)
Signals to notice
largest rectangle of 1s in matrixhistogram per rowstack on each histogram
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).
What must stay true
Each row creates a histogram of consecutive 1s above. Largest rectangle in each histogram is a candidate.
Easy way to go wrong
Not resetting height on 0 — height[j] = 0 when cell is 0.