noodleProblems/
Maximal Square
#156

Maximal Square

AlgorithmmediumArrayDynamic ProgrammingMatrix

You are given an m x n binary matrix where every cell is 0 or 1.

Find the largest square submatrix that contains only 1s — the square's sides must run along the grid's rows and columns (no rotation) — and return its **area** (side length squared).

If the grid has no 1 at all, return 0.

Example cases

  • mixed grid
    in matrix =
    10100
    10111
    11111
    10010
    out 4
    The 2x2 block of 1s at rows 1-2, columns 2-3 is the largest all-1s square; area = 2*2 = 4.
  • no 2x2 square
    in matrix =
    01
    10
    out 1
    The 1s are diagonal, so no square bigger than a single cell is all 1s.
  • single zero cell
    in matrix =
    0
    out 0

Constraints

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] is 0 or 1.
Saved
matrix =
[[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]