168. Maximal Square

Medium · Dynamic Programming

Given an m × n matrix containing only '0' and '1' characters, find the side length of the largest square submatrix that contains only '1's.

A square submatrix is a contiguous rectangular region where all rows and columns have the same length. Return the side length of the largest such square; if no square of '1's exists, return 0.

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: 2
Explanation: The largest square submatrix of '1's has side length 2. For example, the square at rows 1-2 and columns 1-2 contains all '1's.
Example 2
Input: matrix = [['0','1'],['1','0']]
Output: 1
Explanation: The largest square submatrix of '1's has side length 1 (any single '1' cell).

Constraints