221. Maximal Square

221

MediumTwo-Dimensional Dynamic Programming2D dynamic programming on a binary matrixLargest all-ones square DP

Maximal Square

Given an m x n binary matrix of '0' and '1' characters, find the largest square whose cells are all '1' and return its area.

Open official problem prompt ↗

In plain English

Determine the area of the biggest square block containing only 1s inside a binary grid.

Picture it like this

Laying square tiles on a floor of good (1) and broken (0) planks. A tile of side k fits at a corner only if the three tiles touching its top, left, and diagonal already fit at side k-1; the weakest neighbor limits how big you can go.

Example

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4
Why: The largest all-ones square has side 2 (area 4), formed in the lower-middle block of 1s.

Constraints

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

Pattern lesson

See the pattern, then code

Largest all-ones square DP

↗

Two-Dimensional Dynamic Programming

Two changing dimensions, two sequences, grids, or two-index decisions.. The side of the largest square whose bottom-right corner is a '1' cell is one more than the smallest of the squares ending at its top, left, and top-left neighbors. A short neighbor bottlenecks the square.

New words, made simpleKnow these before the algorithm

Square side dp[i][j]: Largest side of an all-ones square whose bottom-right corner is that cell
Three-neighbor min: The bottleneck taken over the top, left, and top-left cells
Padding row/column: An extra zero border so edge cells need no special handling

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Check every square by brute force

Far too slow; rechecks overlapping regions repeatedly.

For each cell try every square size and verify all cells are 1.

Time O((m*n)*min(m,n)^2)Space O(1)

Best choiceSquare-side DP

One pass, constant work per cell, tracks the best side.

Each '1' cell derives its max square side from the min of three neighbors plus one.

Time O(m*n)Space O(m*n), reducible to O(n)

The rule we keep true

Invariant

dp[i][j] equals the side length of the largest square of all 1s whose bottom-right corner sits at matrix[i-1][j-1]; it is 0 whenever that matrix cell is '0'.

Why this is correct

Reasoning

A square of side k with bottom-right corner at a cell requires squares of side at least k-1 ending at the cells immediately above, left, and diagonally up-left; conversely, if all three reach side k-1 and the corner is 1, a side-k square exists. So dp[i][j] = 1 + min of the three, and the max over all cells gives the largest square.

The algorithm in three movesSay these aloud before coding

1Let dp[i][j] be the side length of the largest all-ones square whose bottom-right corner is (i-1, j-1)

dp builds side lengths per cell

2For each '1' cell set dp[i][j] = 1 + min(up, left, up-left)

min(up,left,diag)+1 caps growth

3Track the largest side seen

max side = 2 -> area 4

4Return side squared as the area

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readrow 0 and column 0 of dp

2 · AskHow to avoid edge special cases?

3 · Update statedp border = 0

4 · ResultEdge cells compute normally

Key takeaway

The two central rows; highlighted 1s mark the 2x2 square that yields area 4.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 4-6Padded DP table and best
A zero-padded (m+1)x(n+1) table removes boundary checks; best tracks the largest side.
2
Lines 7-11Grow squares
On a '1', the cell's side is one more than the smallest of its three finished neighbors; best is updated.
3
Lines 12Return area
The answer is the largest side squared.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

An all-zero matrix returns 0
A single '1' returns 1
A full row or column of 1s but no 2D block still caps the side at 1
Rectangular (non-square) blocks of 1s only yield the largest inscribed square

Common beginner mistakes

Returning the side instead of the area (side squared)
Taking max instead of min of the three neighbors, which overcounts
Comparing to the integer 1 instead of the character '1'

Check your understanding

Why is dp[i][j] the minimum of the three neighbors plus one rather than any other combination?

Maximal Square

Maximal Square

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Two-Dimensional Dynamic Programming