435. Biggest Ones Rectangle
A tiler is looking at a floor plan drawn as a grid of characters. A cell marked "1" is a sound tile that can be reused and a cell marked "0" is broken. The tiler wants the biggest axis-aligned rectangular patch of the floor that is made only of sound cells.
Given the grid grid of single-character strings, return the number of cells of the largest rectangle that contains only "1" cells, or 0 if there is no sound cell at all. The rectangle must be made of whole cells and its sides must follow the rows and columns of the grid. The grid has at most 200 rows and 200 columns.
Example 1
- Input:
- grid = [["1","0","1","1","1"],["1","1","1","1","1"],["0","1","1","1","0"],["1","1","1","0","1"]]
- Output:
- 6
- Explanation:
Rows 0 to 1 over columns 2 to 4 form a solid block of 2 rows and 3 columns, 6 cells. Rows 1 to 3 over columns 1 to 2 give 3 x 2 = 6 as well, and nothing larger exists.
Example 2
- Input:
- grid = [["0","1","1"],["0","1","1"],["0","1","1"]]
- Output:
- 6
- Explanation:
The right two columns are completely sound for all three rows, so a 3 x 2 rectangle fits, giving 6 cells.
Constraints
1 ≤ rows, columns ≤ 200
grid[i][j] is "0" or "1"
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(rows * cols)
- Space
- O(cols)