Problems/221. Maximal Square

221. Maximal Square

MediumMatrixDynamic ProgrammingDP

Given an m x n binary matrix filled with characters "0" and "1", find the largest square containing only "1"s and return its area.

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

The largest square is a 2x2 square located on the right side from rows 1 to 2, columns 2 to 4.

Example 2

Input: grid = [ ["0", "1"], ["1", "0"] ]

Output: 1

The largest squares are 1x1 squares of '1's, giving an area of 1.

Example 3

Input: grid = [ ["0"] ]

Output: 0

No '1's exist in the grid, so the maximal square area is 0.

Visualizer

⌥

Visualizer will appear here