DSA problem
Maximal Rectangle
Given an m x n binary matrix of '0's and '1's, find the largest rectangle containing only '1's and return its area.
A brute-force enumeration of all rectangles is O(m^2 * n^2) candidate rectangles, each checked in O(m * n), giving an unworkable O(m^3 * n^3) — actually worse. Even with 2-D prefix sums for O(1) area checks, you still face O(m^2 * n^2) rectangles and O((m * n)^2) total work.
The elegant trick reduces the problem to "Largest Rectangle in Histogram" applied to every row. For each row, build an array heights where heights[j] is the count of consecutive '1's in column j ending at the current row (zero if the current cell is '0'). The largest all-ones rectangle whose bottom edge lies on this row equals the largest rectangle in this histogram. Compute it with the classic monotonic-stack algorithm in O(n) per row.
Summing over rows, total time is O(m * n). The heights array can be reused row to row by incrementing entries with '1' and zeroing entries with '0'. The stack-based histogram subroutine adds a sentinel "0" at the right so all remaining bars are popped at the end. Total: O(m * n) time, O(n) space.
Examples
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]6matrix = [["0"]]0matrix = [["1"]]1Constraints
- rows == matrix.length
- cols == matrix[i].length
- 1 <= rows, cols <= 200
- Each cell of `matrix` is the character '0' or '1'.
- Return the area of the largest all-ones axis-aligned rectangle.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.