176. Maximal Square

MediumDynamic Programming

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

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

Explanation: Rows 1-2 and columns 2-3 form a 2 x 2 block of all 1s, so the area is 4. There is no 3 x 3 block of 1s.

Example 2

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

Output: 1

Explanation: The 1s sit on a diagonal and never touch side by side, so the largest square is a single cell with area 1.

Example 3

Input: matrix = [["0"]]

Output: 0

Explanation: The only cell is 0, so there is no square of 1s.

Constraints

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

How to solve Maximal Square: approach and complexity

2D Dynamic Programming: time, space.

Let dp[i][j] be the side length of the largest all-ones square whose bottom-right corner is (i,j). A cell can extend a square only as far as its top, left, and top-left neighbors all allow — so dp[i][j] = 1 + min of those three (when the cell is '1').

Watch it run step by step