FAANGPrep Sprint
Maximal Square
In an m x n grid of 0s and 1s, find the biggest square made entirely of 1s and return how many cells it covers.
Examples
A 2 by 2 square of 1s ends at (2, 3), so the side is 2 and the area is 4.
No two 1s are adjacent, so the biggest square is a single cell.
There is no 1 anywhere, so there is no square at all.
Problem Understanding
We need to find the largest square of 1s.
Example:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Here, distinct 2x2 squares exist. The largest possible is side length 2. Output area: 4.
Algorithm Strategy
dp[i][j] is the side length of the largest all-ones square whose bottom-right corner is at (i, j). Every square has exactly one bottom-right corner, so scanning every cell considers every square.
Recurrence — when matrix[i][j] == '1':
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
Why a minimum. A square of side k ending at (i, j) needs three squares of side k-1 ending above, to the left, and diagonally up-left — all three at once. The weakest of them caps what you can build, so the new side is the smallest plus one.
A '0' ends no square, so dp is 0 there. The answer is the largest side seen anywhere, squared.
Interactive Visualization
dp[i][j] = THE SIDE OF THE BIGGEST ALL-ONES SQUARE ENDING AT (i, j) · OUTLINED = TOP, LEFT AND DIAGONAL
NEXT CELL
matrix
0
1
2
3
4
0
1
2
3
dp — the side ending here
0
1
2
3
4
0
1
2
3
best side
0
filled
0/20
Answer
—
the rule
0 where the matrix holds '0'
answer = best side squared
Cell (0, 0) holds a '1'
Next
(0, 0) is on the top row, so the biggest square ending there is the cell itself: dp[0][0] = 1
matrix
Two tables: the matrix on the left, unchanged for the whole run, and dp on the right, filling in. The same cell lights in both, so a claimed square can always be checked against the 1s it is made of.
On a growing cell, three neighbours are outlined — top, left and diagonal. The L they make is the reason the rule takes a minimum: the new square has to fit over all three at once.
Try Empty: the answer is 0, and the run never reaches the recurrence.