Maximal Rectangle
Hard · Stack & Strings · Array · Dynamic Programming · Stack · Matrix · Monotonic Stack
Problem
You are given a rows x cols grid matrix whose cells are the characters "0" and "1". Return the area of the largest rectangle (with sides along the grid lines) that contains only "1" cells.
Examples
Input: matrix = [["1","1","0"],["1","1","1"],["0","1","1"]] Output: 4
The top-left and the bottom-right 2 x 2 blocks are all 1s; no rectangle of area 5 or more is.
Input: matrix = [["1","1","1","1"]] Output: 4
The whole row is a 1 x 4 rectangle.
Input: matrix = [["0"]] Output: 0
There is no 1 at all, so the area is 0.
Constraints
- rows == len(matrix), cols == len(matrix[i])
- 1 <= rows, cols <= 200
- matrix[i][j] is '0' or '1'
Approaches
- Baseline: run widths, grown upward from every cell — time O(rows² · cols), space O(rows · cols)
Follow-up
For the largest all-1 square instead of rectangle, a simpler table works: the square ending at (r, c) has side 1 + min(up, left, up-left). And if columns may be reordered freely, each row's heights just need sorting: the tallest k columns can be put side by side.
Related problems
Start free on Cariara · Coding problems · System design studio
