Show problems as
Classic problem #85HardArrayDynamic ProgrammingStackMatrixMonotonic Stack

Maximal Rectangle

Real-world version: Largest Flawless Panel
Tracked in this browser only
Read Maximal Rectangle on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A scanner inspects a sheet of veneer cell by cell and hands you the reading as panel, a grid of one-character strings. panel[i][j] is "1" when that cell of the sheet is flawless and "0" when the scanner found a blemish there. Every row of the reading has the same length.

A cutting machine can punch out one axis-aligned block of cells: pick a run of consecutive rows and a run of consecutive columns, and the block is every cell where the two runs meet. The block is sellable only if every cell inside it is flawless.

Return the number of cells in the biggest sellable block. If the sheet has no flawless cell at all, return 0.

Examples

Example 1

Input
panel = [["0", "1", "1", "0"], ["1", "1", "1", "1"], ["1", "1", "1", "1"], ["0", "1", "1", "0"]]
Output
8

Columns 1 and 2 are flawless down all four rows, giving a 4-by-2 block of 8 cells. The two middle rows offer a 2-by-4 block, also 8, and nothing larger exists because the corners are blemished.

Example 2

Input
panel = [["1", "1", "1"], ["1", "1", "1"]]
Output
6

Nothing is blemished, so the machine punches out the whole sheet.

Example 3

Input
panel = [["0", "0"], ["0", "0"]]
Output
0

Every cell carries a blemish, so no block can be sold.

Constraints

  • rows == panel.length
  • cols == panel[i].length
  • 1 <= rows, cols <= 200
  • panel[i][j] is "0" or "1"

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def largest_flawless_panel(panel: list[list[str]]) -> int:
Java
public int largestFlawlessPanel(char[][] panel)

More on the same topics