Maximal Square
Maximal Square is LeetCode 221 (Medium). You get an m × n grid called matrix whose cells are the characters '0' and '1'.
- Find the largest square, with sides along the grid lines, in which every cell is
'1'. - Return that square's area, not its side length.
- If the grid holds no
'1'at all, the answer is 0.
Both dimensions go up to 300, so the grid can have 90,000 cells. Checking every corner and every size is too slow at that scale; the maximal square LeetCode problem expects one pass over the grid.
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 300
- matrix[i][j] is '0' or '1'.
Intuition
Checking every square directly means picking a corner, a size, and scanning its cells: O(m·n·min(m,n)²). The maximal square dynamic programming idea makes each cell answer a smaller question: how big is the largest all-1 square whose bottom-right corner is right here?
A square of side k ending at a cell needs squares of side k − 1 ending just above it, just left of it and on its diagonal. So the side at a cell is limited by the weakest of those three neighbours, plus one for the cell itself. Each cell's answer comes from three already-solved ones, so a single pass over the grid finds the largest square.
A grid, a shape that must be solid, and "largest" in the question: define dp on the corner where the shape ends and ask which neighbouring shapes it must contain. Count Square Submatrices with All Ones (1277) uses the identical table and sums it instead of taking the max.
Approach
Before reading on, fill the dp values for a 3 × 3 block of all 1s by hand. Then change the centre to 0 and see which values change.
Define the state on the bottom-right corner
dp[i][j] = side of the largest all-1 square whose bottom-right corner is matrix[i-1][j-1]. Use a table with one extra row and column of zeros, so the first real row and column read 0 from outside the grid instead of needing a special case. In the maximal square Python code the table is built with a list comprehension, [[0] * (cols + 1) for _ in range(rows + 1)], so no two rows share one list.
Apply the recurrence
matrix[i-1][j-1] == '0'–dp[i][j] = 0, since no square can end on a 0.matrix[i-1][j-1] == '1'–dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
Fill rows top to bottom and left to right, so the three neighbours are always ready before the cell that reads them. The grid holds characters, so compare with '1', not the number 1.
Track the best side and return its area
Keep best = max(best, dp[i][j]) as you fill the table, since the largest square can end at any cell. The problem asks for area, not side length, so return best * best; returning best itself is a common wrong answer.
Why the minimum of three is exact
- Not larger: if the square here had side
k, the cells above, left and diagonal would each end a square of side at leastk − 1, so the minimum is at leastk − 1. - Not smaller: if all three are at least
k − 1, their squares together cover the wholek × kblock except the corner, which is 1, so ak × ksquare exists.
Reduce to one row, if needed
Each row reads only itself and the row above, so a single array of size n + 1 works. Before overwriting dp[j], its old value is up; save it, because it becomes the diagonal for j + 1. dp[j - 1], already updated, is left. Space drops to O(n).
Maximal Square solution in Python | C++ | Java
dp[i][j] is the side of the largest all-1 square whose bottom-right corner is this cell. A 0 cell can end no square, so it is 0. The extra row and column of zeros on top and left mean the first real row needs no special case.dp[i][j] is the side of the largest all-1 square whose bottom-right corner is this cell. A 0 cell can end no square, so it is 0. The extra row and column of zeros on top and left mean the first real row needs no special case.dp[i][j] is the side of the largest all-1 square whose bottom-right corner is this cell. A 0 cell can end no square, so it is 0. The extra row and column of zeros on top and left mean the first real row needs no special case.Common pitfalls
Returning the side instead of the area
return best
return best * best
dp stores side lengths. The first example's largest square has side 2 and the expected answer is 4.
Comparing with the integer 1
if matrix[i - 1][j - 1] == 1:
if matrix[i - 1][j - 1] == "1":
LeetCode passes characters. "1" == 1 is False in Python, so every cell is skipped and the answer is always 0.
Edge cases
A 2 × 4 block gives side 2, area 4. The minimum over three neighbours stops the square at the shorter side.
Complexity
Maximal square vs related grid problems
Three problems that look alike but need different tools.
| Problem | Shape | Method | Time |
|---|---|---|---|
| Maximal Square (221) | square of 1s | 1 + min(up, left, diag) | O(m·n) |
| Count Square Submatrices (1277) | every square of 1s | same table, return the sum | O(m·n) |
| Maximal Rectangle (85) | rectangle of 1s | histogram per row + monotonic stack | O(m·n) |
Maximal Square FAQ
Can I store the sizes in the matrix itself instead of a dp table?
In Python you can overwrite matrix[i][j] with an int, and it saves the table. In C++ and Java the cells are char, so sizes above 9 would need arithmetic on character codes. Changing the caller's input is also a side effect interviewers often ask you to avoid; the one-row array costs only O(n).
Does the answer change if the grid is not square?
No. The recurrence never assumes m = n; only the upper bound on the side changes, to min(m, n).