Hard

Maximal Rectangle

LAB

Given a binary matrix, return the area of the largest rectangle containing only 1s.

EXAMPLES

Example 1

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

Output
6

FUNCTION SHAPE

matrix: intMatrix→int

SOLUTION NOTE

Reduce 2D to 1D: compress each row into a heights array, then apply Q84. This is the power of problem reduction!

Reveal reference solution +

pythonREFERENCE

def maximalRectangle(self, matrix: List[List[str]]) -> int:
    if not matrix or not matrix[0]:
        return 0

    m, n = len(matrix), len(matrix[0])
    heights = [0] * n
    res = 0

    for i in range(m):
        for j in range(n):
            heights[j] = 0 if matrix[i][j] == '0' else heights[j] + 1
        res = max(res, self.largestRectangleArea(heights))

    return res

TimeO(m * n)

SpaceO(n)

Open on LeetCode ↗