Medium

Maximal Square

LAB

Given a binary matrix, return the area of the largest square 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
4

FUNCTION SHAPE

matrix: intMatrix→int

SOLUTION NOTE

dp(i,j) = side length of largest square with top-left corner at (i,j). A square exists only if current cell is 1 AND squares exist to the right, below, and diagonally.

Reveal reference solution +

pythonREFERENCE

def maximalSquare(self, matrix: List[List[str]]) -> int:
    m, n = len(matrix), len(matrix[0])

    @cache
    def dp(i, j):
        if i >= m or j >= n or matrix[i][j] == '0':
            return 0
        return 1 + min(dp(i+1, j), dp(i, j+1), dp(i+1, j+1))

    res = max(dp(i, j) for i in range(m) for j in range(n))
    return res * res

TimeO(m × n)

SpaceO(m × n)

Open on LeetCode ↗