Hard · Dynamic Programming

Maximal Rectangle

Given a rows × cols binary matrix filled with the characters '0' and '1', return the area of the largest axis-aligned rectangle that contains only '1's.

Examples

Example 1

{
  "matrix": [
    ["1", "0", "1", "0", "0"],
    ["1", "0", "1", "1", "1"],
    ["1", "1", "1", "1", "1"],
    ["1", "0", "0", "1", "0"]
  ]
}

Output: area 6

Example 2

{
  "matrix": [
    ["1", "1", "0"],
    ["1", "1", "1"]
  ]
}

Output: area 4

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.