Maximal Rectangle
hardTime: O(m*n)Space: O(n)
Recognize the pattern
largest rectangle of 1s in matrixhistogram per rowstack on each histogram
Brute force idea
Check every rectangle — O(n²m²).
Better approach
Per-row histogram heights + monotonic stack for largest rectangle. Max across rows. O(mn).
Key invariant
Each row creates a histogram of consecutive 1s above. Largest rectangle in each histogram is a candidate.
Watch out for
Not resetting height on 0 — height[j] = 0 when cell is 0.