All problems

Maximal Rectangle

Hard · stack

You are given a grid of 0s and 1s, arranged in rows and columns. Think of the 1s as floor tiles and the 0s as holes.

Find the largest rectangle made up only of 1s. The rectangle must be axis-aligned, so its sides follow the rows and columns of the grid, and every cell inside it must be a 1.

Return its area, which is the number of cells it covers. If the grid has no 1 at all, return 0.

Examples

Example 1

Input: grid = [[1, 0, 1, 0], [1, 1, 1, 1], [1, 1, 1, 0], [0, 1, 1, 0]]

Output: 6

Rows 1 and 2, columns 0 to 2, form a 2 by 3 block of 1s. Rows 1 to 3, columns 1 to 2, form a 3 by 2 block. Both cover 6 cells and nothing larger exists.

Example 2

Input: grid = [[0, 0], [0, 0]]

Output: 0

There are no 1s.

Example 3

Input: grid = [[1, 1, 1, 1]]

Output: 4

A single row of four 1s is itself a rectangle.

Constraints

• 1 <= len(grid) <= 200 and 1 <= len(grid[0]) <= 200
• Every cell of grid is 0 or 1.
• All rows have the same length.